FOR PUBLICATION
 UNITED STATES COURT OF APPEALS
      FOR THE NINTH CIRCUIT

UNITED STATES OF AMERICA,                   No. 08-10190
                Plaintiff-Appellee,
               v.                             D.C. No.
                                          1:03-cr-00538-HG-3
CHERLYN A. NAPULOU,
                                               OPINION
             Defendant-Appellant.
                                      
       Appeal from the United States District Court
                for the District of Hawaii
         Helen Gillmor, District Judge, Presiding

                  Argued and Submitted
           February 13, 2009—Honolulu, Hawaii

                  Filed February 1, 2010

     Before: Stephen Reinhardt, Sidney R. Thomas, and
              Richard A. Paez Circuit Judges.

                Opinion by Judge Reinhardt




                           1843
1846              UNITED STATES v. NAPULOU




                         COUNSEL

Fernando L. Cosio, Honolulu, Hawaii, for the defendant-
appellant.

Florence T. Nakakuni, Assistant U.S. Attorney, Honolulu,
Hawaii, for the plaintiff-appellee.


                         OPINION

REINHARDT, Circuit Judge:

   The district court revoked Cherlyn Napulou’s supervised
release for associating with Karla Kahau, her “life partner”
and a convicted felon, on three comparatively innocuous
occasions. In addition to sentencing Napulou to prison for
these violations, the district court imposed additional condi-
tions on her supervised release, including forbidding her from
having regular contact with anyone with a misdemeanor con-
viction without the prior permission of the probation office,
and — more important — from maintaining any personal,
telephonic, or written contact with Kahau. We vacate the first
condition as overbroad. We also vacate the second condition
and remand for further proceedings, as we cannot determine
                     UNITED STATES v. NAPULOU                     1847
from the record whether this condition would serve the ends
of deterrence, rehabilitation, or public safety.

I.       Factual Background

   On February 5, 2004, Cherlyn Napulou pleaded guilty to
two counts of distributing methamphetamine.1 She was sen-
tenced to 10 months of imprisonment, followed by six years
of supervised release, and successfully served her term of
confinement. She was less successful, however, with her
supervised release. The district court first revoked that status
in 2005, finding that she failed to submit timely and truthful
written reports, failed to follow the probation officer’s
instructions and failed to answer his inquiries truthfully; it
also found that she associated with a person convicted of a
felony without permission of the probation officer on two sep-
arate occasions, misused a handicap placard and operated a
motor vehicle without a license; finally, it found that she
failed to participate in a substance abuse program, failed to
complete an anger management program, failed to notify the
probation officer at least ten days prior to a change in resi-
dence, and pleaded guilty to abuse of a family member in
state court. She was sentenced to 24 months of imprisonment
and 42 months of supervised release, subject to a number of
standard and special conditions of supervision.

   Napulou again successfully served her term of imprison-
ment. Shortly after her release from prison, however, she
again found herself in district court for violation of the terms
of her supervised release, this time for associating with Karla
Kahau in violation of the overlapping standard and special
     1
   The two counts were: (1) distributing approximately a quarter gram of
a mixture or a substance containing methamphetamine within 1,000 feet
of an elementary school, in violation of 21 U.S.C. §§ 860(a), 841(a)(1)
and 18 U.S.C. § 2, and (2) distributing approximately a quarter gram of
a mixture or a substance containing methamphetamine in violation of 21
U.S.C. §§ 841(a)(1) and 841(b)(1)(c), and 18 U.S.C. § 2.
1848                UNITED STATES v. NAPULOU
conditions that prohibited contact with convicted felons with-
out the prior approval of the probation officer. Napulou and
Kahau, a former felon, had met and developed a close rela-
tionship while incarcerated. They were seen together on three
occasions during Napulou’s supervised release: when Kahau
accompanied Napulou to her intake interview with her sub-
stance abuse counselor; when Kahau visited Napulou’s half-
way house, the Mahoney Hale Community Corrections Cen-
ter, to drop off food; and when they appeared together for an
employment interview.2 Napulou admitted to all of those
encounters, but protested the restriction on their relationship,
stating: “[Kahau] has been a very big support . . . for me in
my life. I mean I’m not going to stop it. I’m sorry, but I’m
not. If she’s going to give me that support and motivate me
to get back out there and get my kids, I’m going to hold on
to that.”

   The district court sentenced Napulou to 10 months impris-
onment for her willful association with Kahau, followed by 32
months of supervised release. The court again imposed sev-
eral special conditions of supervision, including special condi-
tion 8, a prohibition on “regular contact with anyone having
a misdemeanor or felony conviction, without prior permission
of the Probation Office,” and special condition 12, a prohibi-
tion on “any contact telephonic, written or personal with
Karla Kahau.” On appeal, Napulou does not contest her sen-
tence of imprisonment, which she was scheduled to complete
shortly after oral argument, but seeks review of the imposition
of the two special conditions of supervised release.

II.    Analysis

   We review for abuse of discretion the conditions of super-
vised release set by the district court and challenged on this
  2
   In addition, at sentencing, the prosecutor presented evidence that
Napulou had been maintaining daily telephonic contact with Kahau after
her arrest and incarceration for associating with Kahau.
                   UNITED STATES v. NAPULOU                 1849
appeal. See United States v. Goddard, 

, 1089
(9th Cir. 2008).

   The district court “enjoys significant discretion in crafting
terms of supervised release,” as it has “at its disposal all the
evidence, its own impressions of a defendant, and wide lati-
tude.” United States v. Weber, 

, 557 (9th Cir.
2006) (internal quotation marks and citations omitted). In
determining the conditions to be imposed, however, the court
must consider certain factors set forth in 18 U.S.C. § 3553(a),
including “the nature and circumstances of the offense and the
history and characteristics of the defendant” and the need for
the sentence imposed to reflect the seriousness of the offense,
to promote respect for the law, to provide just punishment, to
afford adequate deterrence, to protect the public, and to
encourage rehabilitation. The district court’s discretion is fur-
ther curtailed by 18 U.S.C. § 3583(d), which provides that any
condition must: (1) be reasonably related to the goals of deter-
rence, protection of the public, and/or defendant rehabilita-
tion; (2) involve no greater deprivation of liberty than is
reasonably necessary to achieve those goals; and (3) be con-
sistent with any pertinent policy statements issued by the Sen-
tencing Commission pursuant to 28 U.S.C. § 994(a). See
United States v. Soltero, 

, 866 (9th Cir. 2007),
cert. denied, 

(2008). The government bears the
burden of demonstrating that these statutory standards are
met. 

.

A.   Prohibition on regular contact with anyone having a
     misdemeanor conviction absent prior permission
     from the probation office

   [1] Napulou argues that the restriction on regular contact
with persons convicted of misdemeanors is vague and over-
broad. She contends that it is vague because she could be held
liable for inadvertently associating with someone whom she
did not know had a misdemeanor conviction. Conditions of
supervised release, however, must be interpreted consistently
1850                  UNITED STATES v. NAPULOU
with the “well-established jurisprudence under which we pre-
sume prohibited criminal acts require an element of mens
rea.” United States v. Vega, 

, 750 (9th Cir.
2008). Properly construed, then, the condition regulates only
knowing contact with persons with misdemeanor convictions.
See 

“knowing” element into the condition pro-
hibiting association with members of a criminal gang). In
addition, because this condition proscribes only “regular con-
tact,” any “incidental contacts” without permission do not
violate it. See, e.g., 

(internal punctua-
tion marks omitted) (upholding as valid a condition prohibit-
ing defendant from “associating” with “any known member of
any criminal street gang” because “association” does not
include inadvertent incidental contacts). Given that Napulou
cannot be penalized for incidental contacts or for contacts
with persons whom she does not know have been convicted
of a misdemeanor, this condition is not vague.3

   [2] Although not vague, Napulou is correct that this condi-
tion is overbroad. We have held that the district court may
limit a defendant to associating with “law-abiding” individu-
als, as that limitation is reasonably related to the goals of
rehabilitation and public safety. See United States v.
Furukawa, 

, 922-23 (9th Cir. 1979). But the con-
dition imposed on Napulou is broader than that limitation. As
we recognized in Furukawa, “[a] person disobeying the law
today and hence not being law-abiding may as yet have no
criminal record, and a person with a past record may be
entirely law-abiding today.” 

States v.
Albanese, 

, 546 (2d Cir. 1977)). A person with
a misdemeanor conviction might currently be law-abiding,
and thus may not pose any threat to Napulou’s rehabilitation
or to public safety.
  3
   Moreover, “[i]f and when [supervised release] is revoked, we will . . .
insure that [defendant’s] due process right to notice of prohibited conduct
has been observed and to protect him from unknowing violations.” 

(internal quotation marks and citation omitted).
                   UNITED STATES v. NAPULOU                1851
   [3] This condition is also broader than those terms that
“prevent reversion into a former crime-inducing lifestyle by
barring contact with old haunts and associates, even though
the activities may be legal.” United States v. Bolinger, 

, 480 (9th Cir. 1991). When we have upheld such
restrictions, the barred activity bore a reasonable relationship
to the risk that the defendant would return to his criminal
behavior. See, e.g., United States v. Ross, 

, 721-
22 (9th Cir. 2007) (restricting a defendant who was convicted
of acquiring a firearm for a white supremacist from associat-
ing with known neo-Nazis or white supremacists); United
States v. Romero, 

, 407 (9th Cir. 1982) (prohibit-
ing a drug offender from associating with persons who have
been convicted of drug offenses or with anyone unlawfully
involved with drugs); Malone v. United States, 

(9th Cir. 1974) (prohibiting association with Irish organiza-
tions or visits to Irish pubs where defendant was motivated to
commit his crime because of involvement in the American
Irish Republican movement).

   [4] The restriction on associating with persons with misde-
meanor convictions, by contrast, is not reasonably related to
the risk that Napulou will reoffend. A misdemeanor convic-
tion encompasses a wide range of minor offenses, including,
for example, driving a vehicle without a license. See, e.g.,
State v. Vallesteros, 

, 636 & n.6 (Haw. 1997).
Although Napulou has had her supervised release revoked, in
part for driving without a license, and for stating that an
acquaintance had no criminal record when he had two misde-
meanor convictions, a restriction on association with all per-
sons convicted in the past of a misdemeanor is not reasonably
necessary to prevent her from engaging in criminal behavior
or to protect the public, even though special permission may
be obtained to associate with a particular individual. We
therefore conclude that the district court abused its discretion
in imposing this condition and vacate it.
1852                 UNITED STATES v. NAPULOU
B.     Prohibition on “any contact telephonic, written or
       personal with Karla Kahau”

   Napulou also asks the court to modify the condition prohib-
iting contact with Karla Kahau, her life partner and a con-
victed felon, so that it prohibits only contact initiated by
Napulou.4 In response, the government argues that we should
uphold the condition because the district court correctly deter-
mined that it is reasonably necessary for deterrence, rehabili-
tation, or protection of public safety. The record, however,
does not support the district court’s rationale for imposing the
condition.

   [5] The district judge imposed this condition because she
considered Kahau to be “a good manipulator,” and recalled
that on a previous occasion, when Kahau was granted permis-
sion to associate with another convicted felon, that relation-
ship “devolved into violence.” Apart from the judge’s bare
statements during the revocation hearing, however, the only
specific information in the record regarding a problematic
relationship that Kahau had with another individual is a sen-
tencing report, which shows that, in 2006, the court recom-
mended to the Bureau of Prisons that Kahau “be confined
separately from Casey J. Kealoha.” This recommendation was
made over two years prior to the revocation of Napulou’s pro-
bation, and there is nothing in the record that informs us about
Kahau’s conduct since then. In the time that Kahau has had
a relationship with Napulou, she may have improved her own
behavior and played a constructive role, as Napulou contends,
in shaping Napulou’s conduct and attitudes. Given the signifi-
cant liberty interest at stake, an examination of Napulou and
Kahau’s present circumstances and relationship is required.
  4
    At oral argument, Napulou’s counsel acknowledged that he had not
communicated with his client for some time and did not know the extent
to which Napulou sought that the condition be eliminated or modified. It
appears clear from the record, however, that she wishes to be free of the
restriction entirely.
                      UNITED STATES v. NAPULOU                         1853
See Roberts v. U.S. Jaycees, 

, 618-20 (1984); see
also Fleisher v. City of Signal Hill, 

, 1499-1500
(9th Cir. 1987). The district court’s conclusory statements
regarding Kahau’s prior conduct in an unrelated case are
insufficient to warrant the imposition of special condition 12.
Only an examination of all the relevant facts surrounding the
relationship between Napulou and Kahau by the district judge
will provide a record sufficient to permit the district court,
and a reviewing court, to arrive at an adequate answer as to
whether a judicial prohibition against the intimate relationship
at issue is warranted.

   [6] Although the district court is ordinarily not required to
articulate its reasons for imposing a condition of supervised
release, see 

, we have recognized an
exception to this rule when a condition implicates a “particu-
larly significant liberty interest.” 

on associating
with a “life partner” implicates such an interest. Generally,
when a district court imposes conditions of supervised
release, the conditions must be supported by evidence in the
record,5 and the government must bear its burden of demon-
strating that the conditions satisfy the statutory standards,

. This is particularly true when a spe-
cial condition targets a specific person, and even more so
when that person is the “life partner” of the individual sen-
tenced to supervised release. A condition of supervised
release that prohibits association with convicted felons with-
out the permission of a probation officer is a standard condi-
tion recommended by the Sentencing Commission.6 See U.S.
  5
    The government contends that the probation officer’s statement that
Kahau has a prior drug conviction is sufficient to justify the condition pro-
hibiting Napulou from contact with her. The district judge was not con-
cerned about Kahau’s drug conviction, however, but about her tendency
towards violence — about which we have no evidence other than the
judge’s unexplained general comment regarding Kahau’s behavior on an
earlier occasion.
  6
    Napulou does not challenge on this appeal the imposition of this stan-
dard condition in her case and we intimate no view as to its validity.
1854                  UNITED STATES v. NAPULOU
Sentencing Guidelines Manual § 5D1.3(c)(9) (2008). When,
however, such a condition goes beyond the standard prohibi-
tion on contact with convicted felons, and singles out a person
with whom the individual on supervised release has an inti-
mate relationship, the sentencing court must undertake an
individualized review of that person and the relationship at
issue, and must provide a justification for the imposition of
such an intrusive prohibitory condition. Without a record that
reveals the person’s background, present character, relation-
ship with the defendant, and nexus to defendant’s prospects
for returning to a criminal life, it would be difficult, if not
impossible, to determine whether the district court abused its
discretion in imposing such a condition.

   We recognize that the district judge in this case has made
great efforts over a number of years to support Napulou’s
rehabilitation, and that she is more familiar with Napulou’s
needs than we are. On the record before us, however, it
appears that Napulou and Kahau’s relationship is not founded
on criminality but rather involves productive behavior such as
attending counseling sessions and finding a job. Napulou has
stated that Kahau has been a “very big support” in her life,
and that she would be devastated if she could not continue to
see her. If there is a reason for interfering with Napulou and
Kahau’s relationship that justifies the special condition pro-
hibiting them from contacting one another, regardless of the
nature of the contact and of their progress in achieving reha-
bilitative goals, the government must introduce the appropri-

Napulou challenges only special condition number 12. Whether the special
condition prohibiting Napulou from contact with Kahau is valid will, of
course, answer the question whether Napulou should be allowed to asso-
ciate with Kahau, notwithstanding standard condition number 9, or the
overlapping special condition number 8. Should the district court, upon
developing the facts regarding Napulou’s relationship with Kahau, deter-
mine that Napulou should not be prohibited from associating with Kahau,
there would, of course, be no reasonable basis for the probation officer to
refuse Napulou permission to do so under the other two conditions.
                   UNITED STATES v. NAPULOU                1855
ate evidence that would warrant the imposition of such a
condition. See 

.

   [7] Of course, time has a way of curing all problems.
Napulou was scheduled to complete her sentence of imprison-
ment in February 2009. It may be that by the time this case
is remanded, the relationship will have “devolved into vio-
lence” as the district judge predicted, and Napulou will have
no interest in seeking further contact with Kahau. It might
also be the case, however, that a hearing would show that
their relationship is and will continue to be strong and con-
structive, as Napulou represented at the sentencing hearing. If
Napulou’s representation was correct, we doubt that repeat-
edly incarcerating Napulou for desiring to maintain a relation-
ship with Kahau would best serve the interests of
rehabilitation or deterrence, or would afford greater protection
to the public. We therefore vacate the special condition pro-
hibiting contact with Kahau, as well as the special condition
prohibiting regular contact with individuals with misdemea-
nor convictions, and remand for further proceedings.

  VACATED IN PART and REMANDED.