10046. Derangement

I'm a slow walker, but I never walk backwards.

題目描述

有 $n$ 位同學,使用大寫字母分別標示為 'A''Z'。現在將他們排成一列,由於某些同學個性害羞,不想排第一位 ... 等,請把所有方法數列出來。

如 $n = 3$,A 不排 1、B 不排 2,則有以下幾種排法

BAC
BCA
CAB

方便起見,請按照字典順序輸出。

輸入格式

多組測資,每一組第一行會有兩個整數 $n, \; m$,表示有 $n$ 位同學和接下來有 $m$ 條規則。接下來 $m$ 行,每一行上會有兩個整數 $x, \; y$,表示第 $x$ 位同學不排第 $y$ 個位置。

  • $1 \le n \le 10$
  • $1 \le m \le 100$

輸出格式

對於每一組測資,若有 $P$ 種方法數,則輸出 $P$ 行結果。

範例輸入

3 2
1 1
2 2
 
3 3
1 1
2 2
3 1

範例輸出

BAC
BCA
CAB
BAC
BCA

Discussion