小銘跟浩浩即將展開他們當社會新鮮人的新生活！他們住的國度 — IOIC 國，是一個巨大的島國，其中有 $N$ 座編號為 $1$ 到 $N$ 的島嶼。在這個國度，「順流航運」跟「逆流航運」兩家公司掌握了島嶼之間的船班。順流航運公司有 $M$ 條路線，其中第 $i$ 條路線由 $u_i$ 單向運行至 $v_i$。逆流航運公司也有 $M$ 條路線，而每一條路線恰與順流航運相反。也就是說，第 $i$ 條路線由 $v_i$ 單向運行至 $u_i$。我們可以把順流航運的路線看成有向圖 $G$，那麼逆流航運的路線就是 $G$ 的反圖 $G^ R$。

小銘跟浩浩在考慮要搬到哪一座島嶼，但是他們希望搬家之後仍然可以經常見面。麻煩的是，小銘只能搭乘順流航運的船，浩浩只能搭乘逆流航運的船。假設他們的家在點 $x, y$，那麼他們會用以下方法見面：他們會先決定好一個非負整數 $k$，接下來小銘會搭乘恰 $k$ 艘順流航運的船，浩浩會搭乘恰 $k$ 艘逆流航運的船。換句話說，小銘會選擇一條 $G$ 上的路徑 $x = x_0, x_1, x_2, \dots, x_k$，浩浩會選擇 $G^ R$ 上的路徑 $y = y_0, y_1, \dots, y_k$ 。注意到，他們的路徑可以經過重複的船班和島嶼。如果存在一個 $i$ 使得 $x_i = y_i$，那就代表小銘跟浩浩成功見面。

小銘和浩浩想要知道，選擇 $(x, y)$ 之後，他們最多能夠見面幾次。他們發現有以下三種可能：

• 無法見面：不論他們選擇什麼路徑，都無法見面。
• 見面一次：存在一組路徑讓他們可以在路徑見面恰一次。而且對於所有能讓他們見面的路徑，他們都只能見面一次。
• 見面多次：存在一組路徑，讓他們在路上會見面大於一次。

給定 IOIC 國的航班地圖，請幫他們計算對於所有 $1 \le x, y \le N$ 的 $(x, y)$，見面一次以及見面多次的可能性分別有幾種。