a346. TOI 2021/03 潛力組：延長線

題目描述

音箱插頭與牆面插座的型號同為 T。現有 N 條延長線，第 i 條有型號 A_i 的插座及型號 B_i 的插頭；插頭只能接入相同型號的插座。

由於距離限制，必須把所有 N 條延長線全部串接使用。排列從音箱開始，到牆面結束：第一條延長線的插座必須匹配 T，相鄰延長線須以前一條的插頭匹配後一條的插座，最後一條插頭必須匹配 T。

請判斷是否存在這種串接方式；若指令要求輸出排列，須輸出延長線編號序列中字典序最小的一種。

輸入格式

第一行為 N、C，1 ≤ N ≤ 10^3，1 ≤ C ≤ 2。N 為延長線數，C 為指令。 第二行為 T，1 ≤ T ≤ 10。 接著 N 行依序描述編號 1 到 N 的延長線，第 i 行為 A_i、B_i，分別表示插座與插頭型號，1 ≤ A_i,B_i ≤ 10。同一行整數以空白分隔。

輸出格式

第一行輸出 1 表示有解，或 0 表示無解。 只有 C=2 且有解時，再輸出第二行：從音箱到牆面的 N 個延長線編號，以空白分隔，並取字典序最小的可行排列。C=1 或無解時不輸出第二行。

原題分組限制

六組依序為：5 分 N≤3、C=1；5 分 N≤3、C=2；15 分 N≤10、C=1；15 分 N≤10、C=2；30 分 N≤10^3、C=1；30 分 N≤10^3、C=2。

範例 1

輸入：

5 2
1
1 2
2 1
1 3
2 1
3 2

輸出：

1
1 2 3 5 4

範例 2

輸入：

5 1
1
1 2
2 1
1 3
2 1
3 2

輸出：

1

範例 3

輸入：

4 1
1
1 3
3 1
5 9
9 5

輸出：

0

範例 4

輸入：

4 2
1
1 3
3 1
5 9
9 5

輸出：

0

原題疑義與審核備註

原題輸入段把每行編號寫為 N，依定義與範例整理為第 i 條；第四組範例輸出標頭誤標為「輸出範例 3」，內容仍按第四組原樣保留。

來源

TOI 2021 年 3 月練習賽潛力組，依官方 PDF 整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202103/Extension%20Cord.pdf

標籤：TOI 歷屆