Suuntaamattoman verkon solmupeite on joukko solmuja, jolla vähintään toinen pää jokaisesta kaaresta kuuluu solmupeitteeseen.

Tehtävänäsi on kertoa, onko annetulla suuntaamattomalla verkolla enintään $k$:n kokoinen solmupeite.

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$: solmujen ja kaarten määrä sekä kyselyn parametri $k$.

Seuraavat $m$ riviä kuvaavat verkon kaaria sisältäen kaksi lukua, jotka ovat kaaren päät.

Tuloste

Tulosta "YES", jos verkolla on $k$:n solmun solmupeite. Muuten tulosta "NO".

Rajat

• $1 \le k \le 10$
• $1 \le n, m \le 1000$

Esimerkki

Syöte:

4 4 2
1 2
2 3
3 4
4 1

Tuloste:

YES