考慮一個包含 $n$ 個頂點的無向圖。圖的一個 $k$-著色是指為每個頂點分配 $k$ 種顏色之一。沒有其他限制——即使兩個頂點由一條邊相連，它們也可以被分配相同的顏色。

給定兩種 $k$-著色 $s$ 與 $t$。你想要一步一步地將初始著色 $s$ 轉變為最終著色 $t$。在每一步中，每個頂點可以將其顏色變更為其相鄰頂點之一的顏色，或者保持當前顏色。

形式化地，你需要尋找一個 $k$-著色序列 $C_0, C_1, C_2, \ldots, C_\ell$，使得 $C_0 = s$、$C_\ell = t$，且對所有頂點 $x$，$C_i(x)$ 等於以下兩者之一：

• $C_{i-1}(x)$；或
• $C_{i-1}(y)$，其中 $(x, y)$ 是圖中的一條邊

保證輸入的圖是連通的且沒有自環。請判斷是否可以建構出這樣的序列，如果可以，請輸出其中一種。只要該序列使用的步數不超過 $20\,000$ 步，它不需要是最短的。

例如，假設你需要從左側的初始著色開始，並達到右側的最終著色：

一種解決方案如下：

輸入格式

輸入的第一行包含三個整數 $n$、$m$ 和 $k$。其中 $n$ 為頂點數，$m$ 為邊數，$k$ 為顏色數（$1 \le n, k \le 100$，$0 \le m \le \binom{n}{2}$）。第二行包含 $n$ 個整數，每個整數都在範圍 $[0, k - 1]$ 內，表示初始著色。第三行包含 $n$ 個整數，每個整數都在範圍 $[0, k - 1]$ 內，表示最終著色。接下來的 $m$ 行中，每行包含兩個整數 $x_i$ 和 $y_i$，代表圖中的一條邊（$1 \le x_i, y_i \le n$）。

輸入的圖是連通的。圖中不存在自環或重邊。

輸出格式

如果不存在這樣的序列，輸出 Impossible。否則，輸出一行或多行描述著色序列 $C_0, C_1, C_2, \ldots, C_\ell$（$\ell \le 20\,000$）。每行包含 $n$ 個以單個空格分隔的整數，描述該著色狀態。第一行表示初始著色，最後一行表示最終著色。

你最多可以使用 $20\,000$ 步，因此輸出最多包含 $20\,001$ 行。

範例

輸入格式 1

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

輸出格式 1

0 1 0 1 1 1
1 1 0 1 0 1
1 1 0 0 1 0
1 0 0 0 1 0

範例

輸入格式 2

1 0 2
0
1

輸出格式 2

Impossible

在範例 1 中，在每次展示的變換中，每個頂點要麼保持其先前的顏色，要麼複製相鄰頂點先前的顏色。在範例 2 中，唯一的頂點沒有相鄰頂點，因此無法從顏色 0 變為顏色 1。