# E. Arrange Teams

time limit per test:2 seconds

memory limit per test:64 megabytes

input:standard input

output:standard output

Syrian Collegiate Programming Contest (SCPC) is the qualified round for the Arab Collegiate Programming Contest. Each year SCPC organizers face a problem that wastes a lot of time to solve it, it is about how should they arrange the teams in the contest hall.

Organizers know that they have t teams and n*m tables allocated in n rows and m columns in the contest hall. They don't want to put teams in a random way. Each year SCPC chief judge puts a list of paired teams (list of a,b teams) that should not sit next to each other (because they are so good or so bad!).

if pair (a,b) is in chief judge list, this means that:

- team number a should not sit in-front of team number b

- team number b should not sit in-front of team number a

- team number a should not sit right to team number b

- team number b should not sit right to team number a

Organizers wastes a lot of time to find a good team arrangement that satisfy all chief judge needs. This year they are asking you to write a program that can help them.

Input

First line contains number of test cases. The first line in each test case contains three numbers: (1  ≤  n,m  ≤  11) and (1  ≤  t  ≤  10). Second line in each test case contains (0  ≤  p  ≤  40) number of pairs. Then there are p lines, each one of them has two team numbers a and b (1  ≤  a,b  ≤  t) where a is different than b.

Output

For each test case, print one line contains the total number of teams arrangements that satisfy all chief judge needs (We guarantee that it will be less than 9,000,000 for each test case). If there is no suitable arrangements print "impossible".

Examples

Input

```2
1 3 2
1
1 2
2 2 4
2
1 2
1 3```

Output

```2
impossible```

Note

In test case 1 there are 2 teams and 3 tables in one row at the contest hall. There are only one pair (1,2), so there are 2 solutions:

team1 then empty table then team2

team2 then empty table then team1

In test case 2 there are 4 tables in 2 rows and 2 columns, and there are 4 teams. There is no arrangement that can satisfy chief judge needs.

``` 1 #include <bits/stdc++.h>
2 using namespace std;
4 {
5     int x=0,f=1;
6     char ch=getchar();
7     while(ch<'0'||ch>'9')
8     {
9         if(ch=='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 inline void write(int x)
21 {
22     if(x<0)
23     {
24         putchar('-');
25         x=-x;
26     }
27     if(x>9)
28         write(x/10);
29     putchar(x%10+'0');
30 }
31 int n,m,t,ans;
32 int vis[15][15];
33 bool dp[15][15];
34 inline void DFS(int k)
35 {
36     if(k==t+1)
37     {
38         ans++;
39         return;
40     }
41     for(int i=1;i<=n;i++)
42     {
43         for(int j=1;j<=m;j++)
44         {
45             if(vis[i][j])
46                 continue;
47             if(!dp[vis[i-1][j]][k]&&!dp[vis[i+1][j]][k]&&!dp[vis[i][j-1]][k]&&!dp[vis[i][j+1]][k])
48             {
49                 vis[i][j]=k;
50                 DFS(k+1);
51                 vis[i][j]=0;
52             }
53         }
54     }
55 }
56 int main()
57 {
58     int T,q,x,y;
60     while(T--)
61     {
62         ans=0;
63         memset(dp,0,sizeof(dp));
64         memset(vis,0,sizeof(vis));
69         for(int i=0;i<q;i++)
70         {
73             dp[x][y]=1;
74             dp[y][x]=1;
75         }
76         DFS(1);
77         if(ans!=0)
78             write(ans),printf("\n");
79         else printf("impossible\n");
80     }
81     return 0;
82 }```

0 条评论

## 相关文章

56400

35350

48680

441110

### Pytorch 学习笔记之自定义 Module

pytorch 是一个基于 python 的深度学习库。pytorch 源码库的抽象层次少，结构清晰，代码量适中。相比于非常工程化的 tensorflow，py...

4.5K20

### PHP数据结构（十一） ——图的连通性问题与最小生成树算法（1）

PHP数据结构（十一）——图的连通性问题与最小生成树算法（1） （原创内容，转载请注明来源，谢谢） 一、连通分量和生成树 1、无向图 设E(G)为连通图G的所...

49990

### 每周学点大数据 | No.5算法的分析之图灵机

No.5期 算法的分析之图灵机 小可：那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢？ Mr. 王：有的，这里既然提到了多项式算法和易解难解问题，...

38580

22810

### 数控宏程序的编程及应用

1. 什么场合会用到宏程序编程？ 其实说起来宏就是用公式来加工零件，比如说椭圆，如果没有宏的话，我们要逐点算出曲线上的点，然后慢慢来用直线逼近，如果是个光洁度要...

21480

10330