資訊社一家親,為了加強歷屆所有資訊社社員的羈絆,我們希望能不斷加強人與人之間的關係。
為此,你需要在已知的$\color{black}{\space N\space}$個人(編號$\color{black}{\space 1\sim N\space}$)之間不斷進行以下兩種操作:
1. $\color{black}{\space add\;a\;b\space}$:加強編號$\color{black}{\space a\space}$和$\color{black}{\space b\space}$的關係,好讓資訊社的羈絆更穩固。
2. $\color{black}{\space query\space}$:詢問有多少人$\color{black}{\space x\space}$滿足「存在一對$\color{black}{\space a,b\space}$,無論怎麼沿著人與人之間加強的關係走,都一定得經過$\color{black}{\space x\space}$才能從一方抵達另一方」。也就是當這個人消失,$\color{black}{\space a,b\space}$之間的間接強烈關係就會從原本存在變成斷開,這樣我們可能就得把$\color{black}{\space x\space}$列入觀察名單之中,為了方便起見,請你再由小到大把這些人的編號輸出出來。
奮鬥吧!
輸入首行有一個正整數$\color{black}{\space T(T\leq10)\space}$代表測資筆數。
每筆測資首行有兩個正整數$\color{black}{\space N,Q(N\leq600,Q\leq180300)\space}$,代表要加強關係的資訊社人數和操作次數,其中操作滿足$\color{black}{\space add\space}$操作不會重複加強同樣的兩個人的關係;$\color{black}{\space query\space}$操作不超過$\color{black}{\space 600\space}$次。
接下來$\color{black}{\space Q\space}$行,每行一種操作。
對於每個$\color{black}{\space query\space}$操作,輸出一行,第一個數字$\color{black}{\space k\space}$代表滿足條件的人數,接下來由小到大輸出$\color{black}{\space k\space}$個數字代表滿足條件人們的編號。同一行的所有數字之間以空格隔開。
1 4 8 add 1 2 query add 2 3 query add 3 4 query add 4 1 query
0 1 2 2 2 3 0
範例測資中,第二筆$\color{black}{\space add\space}$操作後滿足$\color{black}{\space 2\space}$號消失後,$\color{black}{\space 1\space}$號和$\color{black}{\space 3\space}$號便從原本存在加強關係的連結轉為不存在,故第二次的$\color{black}{\space query\space}$將輸出$\color{black}{\space 1\;2\space}$,代表有$\color{black}{\space 1\space}$個人需要列入觀察名單,而這個人就是$\color{black}{\space 2\space}$號。
第三筆$\color{black}{\space add\space}$操作後滿足$\color{black}{\space 2\space}$號或$\color{black}{\space 3\space}$號消失後,$\color{black}{\space 1\space}$號和$\color{black}{\space 4\space}$號便從原本存在加強關係的連結轉為不存在,故第三次的$\color{black}{\space query\space}$將輸出$\color{black}{\space 2\;2\;3\space}$,代表有$\color{black}{\space 2\space}$個人需要列入觀察名單,而這$\color{black}{\space 2\space}$個人就是$\color{black}{\space 2\space}$號和$\color{black}{\space 3\space}$號。
第四筆無論讓誰消失,其餘的任兩個人都還是有辦法透過加強後的關係互通,因此沒有人需要列入觀察名單,故第三次的$\color{black}{\space query\space}$將輸出一個$\color{black}{\space 0\space}$。
若使用了複雜度正確的演算法卻獲得TLE,請考慮壓常數。
本題共有三組測試題組,條件限制如下所示。每一組可對應到一或多筆測試資料。
測資點$\color{black}{\space 0(17\%)\space}$:$\color{black}{\space N\leq 50\space}$,$\color{black}{\space query\space}$操作不超過$\color{black}{\space 10\space}$次。
測資點$\color{black}{\space 1(28\%)\space}$:所有$\color{black}{\space query\space}$操作都在$\color{black}{\space add\space}$操作之後,且$\color{black}{\space query\space}$操作只有一次。
測資點$\color{black}{\space 2\sim 3(55\%)\space}$:無特別限制。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
18268 | vincent97198 (好想變強喔) | e199 | 828 | 2019-07-01 13:32 |