在一個神秘國度裡，有 n 座城市，以及 m 條城市與城市之間的雙向道路。下著冷雨的天氣，最適合小偷躲躲藏藏。
故事是這樣的：警察，要抓小偷，可是警察，不知道小偷在哪座城市裡。
每天白晝，小偷會想辦法在一座城市裡面待著。每天深夜，小偷都一定會摸黑離開藏身之處，到達有道路相連(如果有的話)的隔壁城鎮。
每天白晝，警察都會待在某一座城市，盡了全力找尋小偷的蹤跡，如果小偷很不巧地與警察待在同一座城市裡，那麼無論他隱藏地多麼隱密，絕對會被抓到。每天深夜，警察都會連夜搭直升機(外掛)到隨意挑選的另一座城市(也可以是同一座)。
警察和小偷很有默契，他們彼此都知道對方的行動方式。請你幫忙警察算算，究竟有沒有一種方法可以在若干天之後，保證抓得到小偷呢？如果可以的話，也請幫忙找出最壞情形底下，在第幾天才能夠抓得到小偷。
輸入的第一行有一個整數 T (1<=T<=200) 表示有幾組測資。
對於每一組測試資料，第一行有兩個整數 n, m (1<=n<=75000, 0<=m<=75000)。接下來的 m 行，每一行有兩個正整數 a, b (1<=a<b<=n)，表示 a 和 b 這兩座城市之間有直接的道路相連。輸入保證任何兩座城市之間只會有至多一條道路，而且你總是可以從一座城市經過若干條道路後，抵達任何別的城市。
對於每一筆測試資料請輸出兩行，第一行為 "YES" 或 "NO"，分別代表警察一定抓得到小偷，或者運氣不好時一定抓不到。第二行請輸出最壞情況下能抓得到小偷的最少天數，如果是 "NO" 請輸出 -1。答案保證小於 231。
4 3 3 1 2 2 3 1 3 4 3 1 2 3 4 2 4 4 4 1 2 2 3 3 4 4 1 4 3 1 4 3 1 2 3
NO -1 YES 4 NO -1 YES 4
Migrated from old NTUJ.
POI ONTAK 2011
| No. | Testdata Range | Score |
|---|