TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

派大星收集了一堆上好美盤,他希望把這些盤子按照另一個方式排好,但因為他家實在太小了,只有一張餐桌可以放上好美盤,因此他只能用以下的方式整理這些盤子:

原本的盤子從上到下按照了編號 $1, 2, 3, 4, 5, ..., m$ 堆成一疊在餐桌的起始區上,你可以做以下兩種操作

  • 從餐桌的起始區那一疊盤子最上面拿盤子,你可以選擇把這個盤子堆到暫放區目標區的最上面。
  • 暫放區最上面的盤子放到目標區的最上面。

除此之外的操作(譬如說將盤子放到地上或從目標區的盤子拿去別的地方)都因為空間太小所以沒辦法做。換句話說,你只能做以上的兩種操作。

接下來給你一些 $1$ 到 $m$ 的目標排列,求是否可能在有限多的操作內把目標區的盤子排列跟目標排列一樣(給的盤子的順序是由下到上)。此外,必須要回答 $n$ 個這樣的問題才會算 OK。你可以假設每一個問題都是獨立的,也就是說回答每一個目標排列之前,所有的盤子都會再次依照編號回到起始區)。

Input Format

輸入第一行為兩個數字 $m, n$,代表接下來有 $m$ 個上好美盤以及 $n$ 目標排列。
接下來 $n$ 行,每行是一個 $1$ 到 $m$ 的目標排列。

  • $0 < n \leq 10$
  • $0 < m \leq 200000$

Output Format

對每行輸入,若可以達成目標排列則輸出 Y,不可則輸出 N

Sample Input 1

5 2
1 2 3 4 5
5 4 1 2 3

Sample Output 1

Y
N

Sample Input 2

6 3
6 5 4 3 2 1
1 2 3 4 5 6
1 2 3 6 4 5

Sample Output 2

Y
Y
N

Hints

Problem Source

UVA 514

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2