511 . 找錢包

Description

雞塊所住的城市有 $N$$N$ 個十字路口和 $M$$M$ 條路，分別編號 $1$$1$ 到 $N$$N$ 和 $1$$1$ 到 $M$$M$，每條路都是可以雙向通行的。其中有 $K$$K$ 條重要路，這些路是重要幹道，所以你可以從任何十字路口在只通過重要路的情況下走到剩下的所有十字路口。

某一天雞塊要搭高鐵去比賽的時候，發現他的隊友居然把錢包弄丟了！少了大腿隊友的話雞塊會什麼題目都寫不出來，所以雞塊必須去把他的錢包找出來。因為他的隊友只走大路，所以雞塊只需要把所有的重要路都走過就一定可以找到錢包。雞塊現在在 $1$$1$ 號點的高鐵站，並且要走到 $N$$N$ 號點的警察局找他的隊友。

在正要開始走的時候，雞塊不禁產生了一個問題：「是不是能夠在走過每條路不超過一次的前提下走過所有重要路呢？」因為雞塊的智商不足，所以他找上了全營隊的智商天花板，你。

Input Format

第一行有三個整數 $N,M,K$$N,M,K$ 滿足 $2\le N\le 2\times {10}^5,1\le M\le 4\times {10}^5$$2\le N\le 2\times 10^5,1\le M\le 4\times 10^5$ 且 $N-1\le K\le M$$N-1\le K\le M$。

接下來有 $M$$M$ 行，第 $i+1$$i+1$ 行有兩個數字 $u_i,v_i$$u_i,v_i$（$1\le u_i,v_i\le N$$1\le u_i,v_i\le N$），代表第 $i$$i$ 條路連接著第 $u_i$$u_i$ 和 $v_i$$v_i$ 個路口。前 $K$$K$ 條是重要路，剩下的 $M-K$$M-K$ 條是正常路。保證 $u_i<v_i$$u_i<v_i$ 且 $(u_i,v_i)\ne (u_j,v_j)\mathrm{\forall }i\ne j$$(u_i, v_i) \neq (u_j, v_j)\ \forall i \neq j$。

Output Format

如果存在一條這樣的路，輸出 Yes，否則輸出 No。

Sample Input 1

4 4 4
1 2
1 3
2 3
1 4

Sample Output 1

xxxxxxxxxx
Yes

Sample Input 2

xxxxxxxxxx
5 8 5
1 2
2 3
3 4
4 5
3 5
1 4
1 3
1 5

Sample Output 2

xxxxxxxxxx
Yes

Sample Input 3

xxxxxxxxxx
5 4 4
1 2
2 3
2 4
1 5

Sample Output 3

xxxxxxxxxx
No

Subtasks

Testdata and Limits