原題來自：UOJ #117

有一天一位靈魂畫師畫了一張圖，現(xiàn)在要你找出歐拉回路，即在圖中找一個(gè)環(huán)使得每條邊都在環(huán)上出現(xiàn)恰好一次。

一共兩個(gè)子任務(wù)：

這張圖是無向圖。（50 分）

這張圖是有向圖。（50 分）

第一行一個(gè)整數(shù) t，表示子任務(wù)編號。t∈{1,2}，如果 t=1 則表示處理無向圖的情況，如果 t=2 則表示處理有向圖的情況。

第二行兩個(gè)整數(shù) n,m，表示圖的結(jié)點(diǎn)數(shù)和邊數(shù)。

接下來 m 行中，第 i 行兩個(gè)整數(shù) v_i,u_i ，表示第 i 條邊（從 1 開始編號）。保證 1≤v_i,u_i≤n。

如果 t=1 則表示 v_i 到 u_i 有一條無向邊。

如果 t=2 則表示 v_i 到 u_i 有一條有向邊。

圖中可能有重邊也可能有自環(huán)。

如果不可以一筆畫，輸出一行 NO。

否則，輸出一行 YES，接下來一行輸出一組方案。

如果 t=1，輸出 m 個(gè)整數(shù) p₁,p₂,…,p_m 。令 e=|p_i|，那么 e 表示經(jīng)過的第 i 條邊的編號。如果 p_i為正數(shù)表示從 v_e 走到 u_e ，否則表示從 u_e 走到 v_e 。

如果 t=2，輸出 m 個(gè)整數(shù) p₁,p₂,…,p_m 。其中 p_i 表示經(jīng)過的第 i 條邊的編號。

數(shù)據(jù)范圍與提示：

1≤n≤10⁵,0≤m≤2×10⁵

信息學(xué)一本通 圖論 模板