松鼠喜歡吃松果，現在有$N$個小島，以及$M$座小橋，其中橋可以雙向通行，松鼠既不會游泳也不會飛，但他可以通過小橋到每座小島上， 而每座橋上都有一個松果，松鼠想要把所有松果都吃掉，然而每座小橋都只能經過一次，因為走過去後橋就會爆了(松鼠吃太多松果太胖了QAQ)。而在一開始松鼠在編號為$S$的小島上，請問松鼠是否可以吃到所有的松果？如果可以請幫松鼠找出能吃到所有松果的路徑，否則若無法吃到所有松果請輸出"QQ"(不含引號)。
第一行輸入一個正整數$T(T\le 10)$代表測資筆數。
每筆測資第一行輸入兩個正整數$N,M,S(N,M\le 10^5 , 1\le S\le N)$代表島的數量、橋的數量以及起始島嶼編號。
接下來有$M$行每行包含兩個正整數$u_i,v_i(1\le u,v\le N)$代表第$i$座橋連接島嶼$u,v$。
每筆測資輸出一行，若松鼠可以吃到所有松果則輸出$M$個正整數依序為經過的橋的編號(若有多組解請任意輸出一種即可)，反之若無法則輸出"QQ"(不含引號)。
7 4 5 2 1 2 2 4 1 4 2 3 4 3 4 5 1 1 2 2 4 1 4 2 3 4 3 4 4 1 1 2 2 4 4 3 1 3 4 6 1 1 2 1 2 2 3 2 3 2 4 4 2 4 2 1 1 2 3 4 4 1 2 1 2 4 1 3 1 2
1 3 5 4 2 QQ 1 2 3 4 1 3 4 5 6 2 QQ 1 QQ
你寫的演算法的複雜度真的是$O(N+M)$嗎(?)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||