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 conditions on her supervised release, including forbidding her from having regular contact with anyone with a misdemeanor conviction 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 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 sentenced 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 separate 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 residence, 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.

[*1044] Napulou again successfully served her term of imprisonment. 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 conditions that prohibited contact with convicted felons without the pri- or approval of the probation officer. Napulou and Kahau, a former felon, had met and developed a close relationship while incarcerated. They were seen together on three occasions during Napulou’s supervised release: when Kahau accompanied Napulou to her intake interview with her substance abuse counselor; when Kahau visited Napulou’s halfway house, the Mahoney Hale Community Corrections Center, 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 imprisonment for her willful association with Kahau, followed by 32 months of supervised release. The court again imposed several special conditions of supervision, including special condition 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 prohibition on “any contact telephonic, written or personal with Karla Kahau.” On appeal, Napulou does not contest her sentence 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 supervised release set by the district court and challenged on this appeal. See United States v. Goddard, 537 F.3d 1087, 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 latitude.” United States v. Weber, 451 F.3d 552, 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 further curtailed by 18 U.S.C. § 3583(d), which provides that any condition must: (1) be reasonably related to the goals of deterrence, protection of the public, and/or defendant rehabilitation; (2) involve no greater deprivation of liberty than is reasonably necessary to achieve those goals; and (3) be consistent with any pertinent policy statements issued by the Sentencing Commission pursuant to 28 U.S.C. § 994(a). See United States v. Soltero, 510 F.3d 858, 866 (9th Cir.2007), cert. de [*1045] nied, — U.S. -, 129 S.Ct. 35, 172 L.Ed.2d 48 (2008). The government bears the burden of demonstrating that these statutory standards are met. Weber, 451 F.3d at 558.

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

Napulou argues that the restriction on regular contact with persons convicted of misdemeanors is vague and overbroad. 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 with the “well-established jurisprudence under which we presume prohibited criminal acts require an element of mens rea.” United States v. Vega, 545 F.3d 743, 750 (9th Cir.2008). Properly construed, then, the condition regulates only knowing contact with persons with misdemeanor convictions. See id. (reading a “knowing” element into the condition prohibiting association with members of a criminal gang). In addition, because this condition proscribes only “regular contact,” any “incidental contacts” without permission do not violate it. See, e.g., Soltero, 510 F.3d at 866 (internal punctuation marks omitted) (upholding as valid a condition prohibiting 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]

Although not vague, Napulou is correct that this condition is overbroad. We have held that the district court may limit a defendant to associating with “law-abiding” individuals, as that limitation is reasonably related to the goals of rehabilitation and public safety. See United States v. Furukawa, 596 F.2d 921, 922-23 (9th Cir.1979). But the condition 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.” Id. (quoting United States v. Albanese, 554 F.2d 543, 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.

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, 940 F.2d 478, 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, 476 F.3d 719, 721-22 (9th Cir.2007) (restricting a defendant who was convicted of acquiring a firearm for a white supremacist from associating with known neo-Nazis or white supremacists); United States v. Romero, 676 F.2d 406, 407 (9th Cir.1982) (prohibiting a drug offender from associat[*1046] ing with persons who have been convicted of drug offenses or with anyone unlawfully involved with drugs); Malone v. United States, 502 F.2d 554 (9th Cir.1974) (prohibiting association with Irish organizations or visits to Irish pubs where defendant was motivated to commit his crime because of involvement in the American Irish Republican movement).

The restriction on associating with persons with misdemeanor convictions, by contrast, is not reasonably related to the risk that Napulou will reoffend. A misdemeanor conviction encompasses a wide range of minor offenses, including, for example, driving a vehicle without a license. See, e.g., State v. Vallesteros, 84 Hawaii 295, 938 P.2d 632, 636 & n. 6 (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 misdemeanor convictions, a restriction on association with all persons 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.

B. Prohibition on “any contact telephonic, written or personal with Karla Kahau”

Napulou also asks the court to modify the condition prohibiting contact with Karla Kahau, her life partner and a convicted 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 determined that it is reasonably necessary for deterrence, rehabilitation, or protection of public safety. The record, however, does not support the district court’s rationale for imposing the condition.

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 permission to associate with another convicted felon, that relationship “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 sentencing report, which shows that, in 2006, the court recommended 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 probation, 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 significant liberty interest at stake, an examination of Napulou and Kahau’s present circumstances and relationship is required. See Roberts v. U.S. Jaycees, 468 U.S. 609, 618-20, 104 S.Ct. 3244, 82 L.Ed.2d 462 (1984); see also Fleisher v. City of Signal Hill, 829 F.2d 1491, 1499-1500 (9th Cir.1987). The district court’s conclusory statements regarding Kahau’s prior conduct in an unrelated case are insufficient[*1047] 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.

Although the district court is ordinarily not required to articulate its reasons for imposing a condition of supervised release, see Weber, 451 F.3d at 561, we have recognized an exception to this rule when a condition implicates a “particularly significant liberty interest.” Id. A ban 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 demonstrating that the conditions satisfy the statutory standards, Weber, 451 F.3d at 558. This is particularly true when a special condition targets a specific person, and even more so when that person is the “life partner” of the individual sentenced to supervised release. A condition of supervised release that prohibits association with convicted felons without the permission of a probation officer is a standard condition recommended by the Sentencing Commission. ^[6] See U.S. Sentencing Guidelines Manual § 5D1.3(c)(9) (2008). When, however, such a condition goes beyond the standard prohibition on contact with convicted felons, and singles out a person with whom the individual on supervised release has an intimate 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, relationship 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[*1048] 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 prohibiting them from contacting one another, regardless of the nature of the contact and of their progress in achieving rehabilitative goals, the government must introduce the appropriate evidence that would warrant the imposition of such a condition. See Weber, 451 F.3d at 558.

Of course, time has a way of curing all problems. Napulou was scheduled to complete her sentence of imprisonment in February 2009. It may be that by the time this case is remanded, the relationship will have “devolved into violence” 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 constructive, as Napulou represented at the sentencing hearing. If Napulou’s representation was correct, we doubt that repeatedly incarcerating Napulou for desiring to maintain a relationship 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 prohibiting contact with Kahau, as well as the special condition prohibiting regular contact with individuals with misdemeanor convictions, and remand for further proceedings.

VACATED IN PART and REMANDED.