卡卡城裡有各式各樣的單行道，從某個路口連接到另一個路口。為了預防海嘯的來襲，政府制定了疏散計畫。這個疏散計畫當中包含了：每隔幾天就封閉一條道路。你的人現在在編號為 1 的路口，給你封閉危險道路的時間點，你想要知道在某些時候，從編號為 1 的路口緊急疏散至某個路口所需要的最少時間。經過每一條單行道都需要花恰好一分鐘。
輸入的第一行有一個整數 T (1<=T<=30) 表示有幾組測資。
對於每一組測試資料，第一行包含三個正整數 n, m, q (1<=n<=1000; 0<=m<=100000; 1<=q<=200000)，接下來有 m 行，每行有兩個整數 u, v (1<=u, v<=n) 表示有一條單行道從路口 u 通往路口 v。任何兩個路口之間同一個方向至多只有一條單行道。
接下來的 q 行，表示依照時間點出現的事件，每一行的開頭有一個英文字母、以及一個數字 k，若為 'U' (Unfortunately)，表示輸入的第 k 條道路在這時候被封鎖，不再能夠通行。若為 'E' (Evacuation)，表示此時你想要知道通往路口 k 所需的最少時間。
在計算疏散時間時，不必考慮未來道路被封閉的可能性。
對於每一個 'E' 詢問，請輸出對應的答案。若無論如何都沒辦法到達，請輸出 -1。
這題 I/O 量很大。
Migrated from old NTUJ.
POI ONTAK 2011
| No. | Testdata Range | Score |
|---|