Description

底下三種瓷磚的大小都是1*1, 我們用底下三種瓷磚構造出一個n*m的棋盤.這個棋盤的最左上角為(1,1), 最右下角為(n,m).

+---+ +---+ +---+
|   | |   | |   |
|   | |** | |***|
|   | | * | |   |
+---+ +---+ +---+
Type1 Type2 Type3
我們定義(1,1) 為起點, (n,m) 為終點.

對於每一塊瓷磚我們可以任意旋轉, 但是不能移動它的位置, 藉由每一塊瓷磚的旋轉, 我們有機會構造出一條從起點到終點的路線! 如下圖 :

而這一題的任務很簡單, 就是讀入一個這樣的棋盤, 然後輸出是否有機會從起點到達終點.

Input

輸入第一行為測資數 T, 接下來有T筆測資.

每筆測資第一行為兩個整數n m (n,m <= 8)
接下來就是一個n*m的棋盤, 每個1*1的單位如上所述, 一定是三種type之一.
請參考sample input.

Output

每筆測資輸出一行.
如果可以到達終點輸出YES
否族輸出NO

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

有三件事情一直讓ylc感到很困擾，第一就是她的方向感奇差，下了公車常常走錯方向，在巷子裡轉超過三個彎一定走不回來，最扯的是念清大三年有時候還是會在宵夜街迷失方向。而且她很不會看地圖，就算有google map也沒用，唯一的優點大概是因此練就了一身問路的本領。每次ylc要出去玩，她的爸媽就會提心吊膽擔心她把自己弄不見。但是今天ylc出門的時候，她沒有把自己弄不見，反而是把回家的鑰匙搞丟了！這就是第二件讓她困擾事：常常弄丟東西。ylc回家需要開三道門，分別需要'Y', 'L', 'C'這三把鑰匙。由於ylc實在太常把鑰匙弄丟，她今天出門就是為了把這三把鑰匙各複製一份，沒想到拿到複製的鑰匙後，還沒回到家，這六把鑰匙就通通被她弄不見了。如果告訴爸媽鑰匙又不見了，爸媽一定會大發雷霆，因此ylc決定她至少要把這三把鑰匙各找回一個。但是她實在是太路癡了沒辦法自己去尋找，所以她發揮了強大的問路本領，請你幫助她。給你一張地圖，有這六把鑰匙所在的位置，你可以告訴ylc她至少需要走多久才可以找回三把鑰匙嗎?ylc可以往上、下、左、右、左上、左下、右上、右下八個方向走，除了以'#'代表的牆壁之外其他的路她都可以走。
噢對了第三件讓ylc困擾的事情就是她很龜毛，她一定要先找到'Y'再找'L'最後才肯去找'C'，所以你也必須幫助她按照這個順序找回鑰匙，如果ylc在找到'L'之前就經過'C'，她也一定要等到拿到'L'才肯回來拿'C'喔~

Input

有多組測資。
每組測資第一列有兩個數字M, N。代表地圖的大小是M*N。 1<=M, N<=300。
接下來會有M列，每列有N個字元，是地圖的樣子。地圖上只會有5種字元：
'.' : 可以走的路。
'#' : 牆壁，不能走。
'Y' : 'Y'這把鑰匙的位置，每張地圖中都會出現恰好兩次。
'L' : 'L'這把鑰匙的位置，每張地圖中都會出現恰好兩次。
'C' :'C'這把鑰匙的位置，每張地圖中都會出現恰好兩次。

Output

請從任一個'Y'開始，計算ylc要走幾步才能夠走到任一個'L'，再走到任一個'C'。
有八種可能的答案，只需要輸出步數最少的那個。
如果ylc可以順利找回三把鑰匙，輸出" YLC can be found in x steps :) "，x是最少所需的步數。
如果ylc沒辦法找回三把鑰匙，輸出" OH NO! YLC can't be found :( "。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

二元搜尋樹（Binary Search Tree），也稱有序二元樹（ordered binary tree）,排序二元樹（sorted binary tree），是指一棵空樹或者具有下列性質的二元樹：
1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2. 任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3. 任意節點的左、右子樹也分別為二元搜尋樹。
4. 沒有鍵值相等的節點（no duplicate nodes）。

給你 n 個相異的整數，你能找到多少棵由這 n 個整數組成的二元搜尋樹？

舉例來說，由{1, 2, 3} 這 3 個數所組成的二元搜尋樹共有以下5種。

Input

每組測資有一個正整數 n (0 < n < 1000)，代表那種二元搜尋樹由 n 個相異的整數所組成。

Output

對於每組測資請單行輸出一個整數，代表符合條件的二元搜尋樹個數。
由於答案可能很大，請輸出答案除以 100000007 的餘數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Mimi, Moumou兩人是青梅竹馬，從小就玩在一起（雖然他們現在也才小學三年級而已）。愛玩的兩人，平常的遊戲玩久了之後就覺得無聊沒勁，常常湊在一起發明新的遊戲。

這天他們又開始在設計新遊戲了，遊戲的規則如下：

1.     先在地上畫N個圓圈，編號1到N，並規定1號圓圈是起點、N號是終點

2.     在這N個圓圈之間任意互相畫”單向”箭頭，箭頭起點和終點各有一圓圈且兩圓圈不為同一圓，假設有一箭頭從圓a連到圓b，則遊戲中可以從a跳到b。

3.     檢查1, 2步驟所畫出的圖，確保任何編號1 ~ N-1的圓都有路徑可以走到終點，同時圖中也不可以有迴圈產生（也就是對於任何一個圓，絕對不會有路徑可以從自己走到自己），對任兩圓a, b最多只有一個箭頭從a指向b。

4.     兩個人進行遊戲，開始時先由一人站在起點（1號圓），另一個人站在圖外。

5.     遊戲中假設甲站在一個圓 C 中而乙在圖外，則乙要從 C 所指出去的箭頭中選一個箭頭，站到這個箭頭所指的圓上，然後甲則離開C走到圖外。

6.     兩人重複步驟5的動作，直到其中一人到達終點，到達終點的人為贏家。

例如下圖：

N = 5，假設由Mimi開始，且遊戲過程為

Mimi 在 1, Moumou 到 2, Mimi 到 3, Moumou 到 5 遊戲結束，由Moumou獲勝。

Input

每筆測資會有多行。
第一行會有兩個整數，分別為N,M。
之後會有M行，每行有兩個整數A,B，
代表A到B有一個單向的箭頭。
之後會有一行Mimi或Moumou，
代表遊戲一開始誰站在起點。
測資保證沒有不符合題目的測資。
當遇到N,M均為0時，代表測資結束。

N<=10000
1<=A,B<=N

Output

對於每一筆測資，假設兩人在挑選圓圈時，均使用對自己最有利的方式進行，
請輸出這組測資中，勝利的人是誰。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

熊貓大學不僅頒發了學生證給圓仔，也頒發給許許多多隻其他的熊貓，並且在山坡上蓋了N棟新的系館。原本這N棟系館兩兩都有路直接相連，但是圓仔和他的朋友們實在太重又太好動，把一堆路都踩壞了(壞到完全無法修復的地步!!)，只剩下M條道路勉強還可以行走。動物保護協會要求熊貓大學必須要重新整修這M條道路，否則會危害到熊貓的安全。熊貓大學整天嚷嚷著沒有錢，當然不願意M條道路都維修，學校希望維修費越少越好，他們只願意花最少的錢，讓每棟系館都有路可以通到所有其他的系館(不一定要直接相連)。學校找來了承包商負責這項工程，修一條道路的價格，和這條路連結的兩棟系館的熊貓數量有關，假設系館a的熊貓數量是Num_a, 系館b的熊貓數量是Num_b，則維修連結a和b的道路所需經費為max(Num_a, Num_b)。
但這個承包商特別喜歡質數，所以替學校打了折扣：如果Num_a或Num_b至少有一個是質數，則維修費用只需要min(Num_a, Num_b)。現在給你N棟系館的熊貓數量，和這M條邊的資訊，你可以算出學校最少要花多少錢維修道路嗎?

Input

多組測資。
每組測資第一列為兩個整數N和M，N代表系館的數量，系館編號為1~N。M代表需要維修的道路數量。1<=N<=500, 1<=M<=N*N/2。
第二列有N個整數，分別代表第1~N棟系館的熊貓數量，每棟系館最多有1000000隻熊貓。
接下來M列為M條道路的資訊。每列有兩個整數a, b，代表這條道路連接第a棟和第b棟系館。 1<=a,b<=N。
測資間會有一空白列。

Output

每組測資請輸出一列，為熊貓大學最少需要支付的維修金額。若不管在這M條道路中選擇多少條，學校都無法讓每棟系館都有路通到所有其他的系館，請輸出"No Solution"。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

S------O----O---E
       |    |
S---O--O-O--O-O-E
    |    |    |
S---O----O----O-E

S---O----O-----O---O--E
    |    |     |   |
S-O-O----O--O--O-O-O--E
  |         |    | 
S-O---------O----O----E

相信大家都有玩過如上圖的抽籤的遊戲。
遊戲的規則非常簡單
1. 從最左方開始任選一個S當作起點。
2. 之後開始向右方前進，每次遇到轉角時，
就必須順著轉角的線移動到另一條線上。
3. 反覆重複步驟2，直到走到其中一個E為止。

現在，給你一張這樣的抽籤遊戲圖，
請你輸出每個S的行進路線，以及他會到達的終點編號。

Input

有多筆測資，每筆測資有多行。
第一行會有兩個正整數N,L,Q，分別表示抽籤圖的橫線數量，圖的總長度，以及所要詢問的路徑數量。
接著，對於每條橫線，會有兩行來描述轉角的情況。
第一行代表該條橫線上轉角的數量C_i。
第二行會有C_i組數對，每組數對由兩個正整數X,Y組成，X代表轉角距離左方的距離，
Y代表該轉角所連到的另一條橫線。
數對會按照順序由X小到大排序，並且對於每條橫線同一個X上最多只會有一個轉角。
轉角的線必定垂直於橫線，並且長度為1(僅能往上或往下一條線移動)。
接下來一行會有Q個正整數，每個整數代表詢問的起點位置。

2<=N,L<=100000
2<=X<=L-1
1<=Y<=N
直線的總數量<=100000
1<=Q<=50

Output

對於每筆測資先輸出一行"Graph #i:"，其中i代表第幾組側資。
接著對於該測資的每一個Q，依照給予的起點順序，依序輸出在抽籤圖中行走的路徑，
及最後到達的終點編號(請參考Sample Output)。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Vasya went for a walk in the park. The park has n glades, numbered from 1 to n. There are m trails between the glades. The trails are numbered from 1 to m, where the i-th trail connects glades xi and yi. The numbers of the connected glades may be the same (xi = yi), which means that a trail connects a glade to itself. Also, two glades may have several non-intersecting trails between them.

Vasya is on glade 1, he wants to walk on all trails of the park exactly once, so that he can eventually return to glade 1. Unfortunately, Vasya does not know whether this walk is possible or not. Help Vasya, determine whether the walk is possible or not. If such walk is impossible, find the minimum number of trails the authorities need to add to the park in order to make the described walk possible.

Vasya can shift from one trail to another one only on glades. He can move on the trails in both directions. If Vasya started going on the trail that connects glades a and b, from glade a, then he must finish this trail on glade b.

Input

 The first line contains two integers n and m (1 ≤ n ≤ 106; 0 ≤ m ≤ 106) — the number of glades in the park and the number of trails in the park, respectively. Next m lines specify the trails. The i-th line specifies the i-th trail as two space-separated numbers, xi, yi (1 ≤ xi, yi ≤ n) — the numbers of the glades connected by this trail.

Output

 Print the single integer — the answer to the problem. If Vasya's walk is possible without adding extra trails, print 0, otherwise print the minimum number of trails the authorities need to add to the park in order to make Vasya's walk possible.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

首先我們定義一個爪子的長相 :
一個爪子包含4個點, 假設編號為1到4
則這個爪子有三條邊 :
1 2
1 3
1 4
一個爪子會如上所述.

現在題目會給你一張無向圖, 每個點的度數都是三. (每個點有三條邊連接)
請問這張圖是否可以分解成一堆爪子??
爪子的點可以共用, 但是每條邊只能出現在一個爪子裡.

以第一組測資為例, 可以有三個爪子, 分別是
一.
6 4
6 5
6 2
二.
1 2
1 4
1 5
三.
3 4
3 2
3 5
可以發現編號4的點就被三個爪子共用.

Input

輸入會有多組測資.

每組測資第一行為一個數字V, 代表圖的點個數 (4<=V<=300)
接下來每行有兩個數字a b , 代表編號a和編號b之間有一條邊 (1<=a,b<=V)
當a,b 都為0時表示這組測試資料的邊都讀完了.

當V = 0時表示測資結尾.

詳細請參考sample input.

Output

每組測資輸出一行.
如果圖可以拆解成許多爪的話輸出YES, 否則輸出NO.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

大家都知道搗蛋是一個非常邪惡的桌遊玩家，這次他決定開發一個可以洗腦對手的工具，令對手不自覺的幫助搗蛋取得勝利。這個工具會在收到搗蛋以數字編輯成的指令後，經過一連串的分解，轉成只由0~2組成的數字，並灌輸至對手的腦波內，來達到控制思想的目的。
分解的過程如下：
1.將輸入的指令視為一個數字N
2.如果N是3的倍數，那麼將N分解成N/3-1和N/3+1。
不是3的倍數，那麼將N變為N+1。
3.持續重複分解的動作，直到要被分解的數小於或等於2。
4.最後將這些分解出來的數字依分解順序印出來，就可以得到控制對手所需要的數字了。
現在，請你幫助搗蛋完成分解的工作吧！





範例：

Input

會有多組測資，每組測資會有一行數字N。1<=N<=10000

Output

對於每筆測資，輸出可以控制別人思想的數字。

Sample Input  Download

Sample Output  Download

Tags

Discuss