你聽過多層次傳銷嗎？這是一種商業行銷模式。

在這個系統裡，有一個發起人，是第一個會員。每個會員都可以去招攬新的會員，一旦A成功招攬到了B，則A是B的「介紹人」，B成為A的「下屬」。此時B也成了會員，可以去招攬更多的會員。在這個層次分明的結構裡，每一個會員可以有很多個下屬，但每一個會員只會有一個介紹人（發起人除外，他沒有介紹人）。

此外，我們將一個會員的所有下屬、所有下屬的所有下屬、……等等，全部統稱為該會員的「下線」。每個會員都可以從他任何下線的購買行為獲得利潤。

現在Phh多層次傳銷公司（以下簡稱P公司）共有N個會員。為了增加上下屬之間的溝通，也為了推銷他們的產品，P公司會不定期地舉行一個活動。每一次活動開始時，P公司會挑選一個「特派會員」，並交給他一張宣傳單。只要特派會員成功把這張宣傳單給他的每一個下線簽名，就視為「任務完成」，並且可以獲得鉅額獎金，他的下線也可以獲得分紅。

然而，為了驗證這張宣傳單確實有達到功能，P公司規定了宣傳單的傳遞與簽名方法：一律採用郵寄傳遞。並且，任何一個會員（包括特派會員本人）收到這張宣傳單之後，如果之前還沒簽過名，就必須在上面簽名；接著，只能把這張宣傳單寄給介紹人或任意一個下屬。
（要注意的是，不能將宣傳單直接寄給介紹人的介紹人，或者下屬的下屬等等。）
當然，如果特派會員收到宣傳單時，上面已經有所有下線的簽名，則任務完成，可以向P公司領取獎金。

P公司推動這個活動的負責人Remal，將所有會員編為0到N-1號，特別地，0號會員代表發起人。他也預先調查了所有會員的從屬關係，並且發現：對於任何兩人A, B使得A是B的介紹人，則宣傳單無論是從A寄到B、或是從B寄到A，都會花費M_AB天的通信時間。

為了決定這個活動要挑選哪個會員做為「特派會員」可以讓宣傳效果最好，Remal想要知道如果挑選某個會員作為特派會員，則最少要經過幾天才能完成這個簽名任務。
然而，會員有時候會搬家，因此寄信時間也會發生改變，因此他還希望可以隨時改變兩人間通信時間的值，以方便未來的查詢。

而身為P公司的資訊管理者，你的任務就是幫助Remal寫一個查詢的程式。
為了你的方便，你可以假設任何會員收到宣傳單之後都可以立刻簽完名並寄出去。