TGU寒假训练营

A - Heron and His Triangle

https://vjudge.net/contest/354911#problem/A

A triangle is a Heron’s triangle if it satisfies that the side lengths of it are consecutive integers t−1, t, t+ 1 and thatits area is an integer. Now, for given n you need to find a Heron’s triangle associated with the smallest t bigger
than or equal to n.

Input
The input contains multiple test cases. The first line of a multiple input is an integer T (1 ≤ T ≤ 30000) followedby T lines. Each line contains an integer N (1 ≤ N ≤ 10^30).

Output

For each test case, output the smallest t in a line. If the Heron’s triangle required does not exist, output -1.

首先，根据题意，得出算法-第一周 - 图1关于算法-第一周 - 图2的式子算法-第一周 - 图3，若使算法-第一周 - 图4为整数，则算法-第一周 - 图5应满足算法-第一周 - 图6，然后用我那可怜的数学，得出算法-第一周 - 图7。（也可以去找规律）

因为我C++大数用的不熟，所以我选Java来写

  1. import java.math.BigInteger;
  2. import java.util.Scanner;
  4. class p{
  5.     private BigInteger p;
  6.     private String zqa(BigInteger n, BigInteger m){
  7.         BigInteger lll=m.multiply(new BigInteger("4")).subtract(n);
  8.         if(p.compareTo(lll) < 1)return lll.toString();
  9.         return zqa(m,lll);
  10.     }
  11.     p(){
  12.         Scanner scan = new Scanner(System.in);
  13.         int l = scan.nextInt();
  14.         int k=0;
  15.         while(k++<l){
  16.             BigInteger r = scan.nextBigInteger();
  17.             if(r.compareTo(new BigInteger("4")) < 1) {
  18.                 System.out.println(4);
  19.             }else if(r.compareTo(new BigInteger("14")) < 1) {
  20.                 System.out.println(14);
  21.             }else {
  22.                 this.p=r;
  23.                 System.out.println(zqa(new BigInteger("4"),new BigInteger("14")));
  24.             }
  25.         }
  26.     }
  27. }
  28. public class Main {
  29.     public static void main(String[] args) {
  30.         new p();
  31.     }
  32. }

感觉这道题也可以用矩阵快速幂。再贴一个刚写的矩阵快速幂的（然而这个超时了，靠）

后来想了一下啊，矩阵快速幂适用于要幂好多次的递推的情况，其原理是一个优化后的递推，这个题里无需幂好多次，只是单纯的一个递推，用矩阵快速幂实际上是画蛇添足了。

  1. import java.util.*;
  3. class M {
  4.     long[][] m = new long[2][2];
  5. }
  7. class p {
  8.     private long mod = 2147493647L;
  11.     private M zqa(M x, M y) {
  12.         M ret = new M();
  13.         for (int i = 0; i < 2; i++) {
  14.             for (int j = 0; j < 2; j++) {
  15.                 ret.m[i][j] = 0;
  16.                 for (int k = 0; k < 2; k++) {
  17.                     ret.m[i][j] = (x.m[i][k] * y.m[k][j] + ret.m[i][j]) % mod;
  18.                 }
  19.             }
  20.         }
  21.         return ret;
  22.     }
  24.     private M pow_M(M a, long zqazqa) {
  25.         M ret = new M();
  26.         Arrays.fill(ret.m[0],0);
  27.         Arrays.fill(ret.m[1],0);
  28.         for (int i = 0; i < 2; i++) ret.m[i][i] = 1;
  29.         while (zqazqa != 0) {
  30.             if ((zqazqa & 1) != 0) ret = zqa(ret, a);
  31.             a = zqa(a, a);
  32.             zqazqa >>= 1;
  33.         }
  34.         return ret;
  35.     }
  36.     p() {
  37.         Scanner scan=new Scanner(System.in);
  38.         int t=scan.nextInt();
  39.         while (t--!=0) {
  40.             long  m=scan.nextLong(),f1=4, f2=14;
  41.             if (m <= 4) System.out.println(f1);
  42.             else if (m <= 14) System.out.println(f2);
  43.             else {
  44.                 M a=new M();
  45.                 Arrays.fill(a.m[0],0);
  46.                 Arrays.fill(a.m[1],0);
  47.                 a.m[0][0] = f2;
  48.                 a.m[1][0] = f1;
  49.                 M b =new M();
  50.                 b.m= new long[][]{
  51.                         {4, -1},
  52.                         {1, 0}
  53.                 };
  54.                 while (a.m[0][0]<m)a = zqa(b, a);
  55.                 System.out.println(a.m[0][0]);
  56.             }
  57.         }
  58.     }
  59. }
  61. public class Main {
  62.     public static void main(String[] args) {
  63.         new p();
  64.     }
  65. }

B - Little Boxes

https://vjudge.net/contest/354911#problem/B

Little boxes on the hillside.
Little boxes made of ticky-tacky.
Little boxes.
Little boxes.
Little boxes all the same.
There are a green boxes, and b pink boxes.
And c blue boxes and d yellow boxes.
And they are all made out of ticky-tacky.
And they all look just the same.

Input

The input has several test cases. The first line contains the integer t (1 ≤ t ≤ 10) which is the total number of test cases.For each test case, a line contains four non-negative integers a, b, c and d where a, b, c, d ≤ 2^62, indicating the numbers of green boxes, pink boxes, blue boxes and yellow boxes.

Output

For each test case, output a line with the total number of boxes.

这个题就是考个大数加减……..就正常做，我先拿java试了一下

  1. import java.math.BigInteger;
  2. import java.util.*;
  3. public class Main {
  4.     public static void main(String []args){
  5.         Scanner kb=new Scanner(System.in);
  6.         int n=kb.nextInt();
  7.         while (n--!=0){
  8.             System.out.println(new BigInteger(kb.next())
  9.                     .add(new BigInteger(kb.next()))
  10.                     .add(new BigInteger(kb.next()))
  11.                     .add(new BigInteger(kb.next())));
  12.         }
  13.     }
  14. }

又用c++写了一个

  1. # include<cstdio>
  2. # include<cstring>
  3. # include<cstdlib>
  4. #include<iostream>
  5. using namespace std;
  6. void add(char* a,char* b,char* c)
  7. {
  8.     int i,j,k,zqazqa1,zqazqa2,temp;
  9.     char *s,*zqa1,*zqa2;
  10.     zqazqa1=strlen(a);
  11.     zqazqa2=strlen(b);
  12.     if (zqazqa1<zqazqa2)
  13.     {
  14.         temp=zqazqa1;
  15.         zqazqa1=zqazqa2;
  16.         zqazqa2=temp;
  17.         zqa1=b;
  18.         zqa2=a;
  19.     }
  20.     else
  21.     {
  22.         zqa1=a;
  23.         zqa2=b;
  24.     }
  25.     s=(char*)malloc(sizeof(char)*(zqazqa1+1));
  26.     s[0]='0';
  27.     for (i=zqazqa2-1,j=zqazqa1-1,k=zqazqa1;i>=0;i--,j--,k--)
  28.         s[k]=zqa2[i]-'0'+zqa1[j];
  29.        for (;j>=0;j--,k--)
  30.            s[k]=zqa1[j];
  31.     for (i=zqazqa1;i>=0;i--)
  32.         if (s[i]>'9')
  33.         {
  34.             s[i]-=10;
  35.             s[i-1]++;
  36.         }
  37.     if (s[0]=='0')
  38.     {
  39.         for (i=0;i<=zqazqa1;i++)
  40.             c[i-1]=s[i];
  41.            c[i-1]='\0';
  42.     }
  43.     else
  44.     {
  45.         for (i=0;i<=zqazqa1;i++)
  46.             c[i]=s[i];
  47.            c[i]='\0';
  48.     }
  49.     free(s);
  50. }
  51. int main()
  52. {
  53.     int n;
  54.     cin>>n;
  55.     while(n--)
  56.     {
  57.         char a[100];
  58.         cin>>a>>b>>c>>d;
  59.         add(a,b,zqa);
  60.         add(zqa,c,zqa);
  61.         add(zqa,d,zqa);
  62.         cout<<zqa<<endl;
  63.     }
  64.     return 0;
  65. }

C - Rabbits

https://vjudge.net/contest/354911#problem/C

Here N (N ≥ 3) rabbits are playing by the river. They are playing on a number line, each occupying a different integer. In a single move, one of the outer rabbits jumps into a space between any other two. At no point may two rabbits occupy the same position.
Help them play as long as possible

Input

The input has several test cases. The first line of input contains an integer t (1 ≤ t ≤ 500) indicating the number of test cases.For each case the first line contains the integer N (3 ≤ N ≤ 500) described as above. The second line contains n integers [Math Processing Error]a1 < [Math Processing Error]a2 < [Math Processing Error]a3 < … < [Math Processing Error]aN which are the initial positions of the rabbits. For each rabbit, its initial position
[Math Processing Error]ai satisfies 1 ≤ [Math Processing Error]ai ≤ 10000.

Output

For each case, output the largest number of moves the rabbits can make.

这个题就是从数组两头看一下，在最靠两个边缘的两个空隙如果距离边缘只有都一个格的话，取其大者，然后把上下的空加起来就可以了。

（人生苦短，我用Java）

  1. import java.util.Scanner;
  3. class p{
  4.     p(){
  5.         Scanner scan = new Scanner(System.in);
  6.         int l = scan.nextInt();
  7.         int k=0;
  8.         while(k++<l){
  9.             int length=scan.nextInt();
  10.             if(length==1||length==2) {
  11.                 System.out.println(0);
  12.             }else if(length==3){
  13.                 int q=scan.nextInt();
  14.                 int m=scan.nextInt();
  15.                 int lll=scan.nextInt();
  16.                 System.out.println(Math.max(m-q-1,lll-m-1));
  17.             }else {
  18.                 int q=scan.nextInt();
  19.                 int m=scan.nextInt();
  20.                 q=m-q-1;
  21.                 int s=0,z;
  22.                 for(int kkk=0;kkk<length-3;kkk++){
  23.                     z=scan.nextInt();
  24.                     s+=(z-m-1);
  25.                     m=z;
  26.                 }
  27.                 int lll=scan.nextInt();
  28.                 System.out.println(s+Math.max(q,lll-m-1));
  29.             }
  30.         }
  31.     }
  32. }
  33. public class Main {
  34.     public static void main(String[] args) {
  35.         new p();
  36.     }
  37. }

D - Tree

https://vjudge.net/contest/354911#problem/D

Consider a un-rooted tree T which is not the biological significance of tree or plant, but a tree as an undirected graph in graph theory with n nodes, labelled from 1 to n. If you cannot understand the concept of a tree here, please omit this problem.
Now we decide to colour its nodes with k distinct colours, labelled from 1 to k. Then for each colour i = 1, 2, · · · , k, define Ei as the minimum subset of edges connecting all nodes coloured by i. If there is no node of the tree coloured by a specified colour i, Ei will be empty.
Try to decide a colour scheme to maximize the size of E1 ∩ E2 · · · ∩ Ek, and output its size.

Input

The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the total number of test cases.
For each case, the first line contains two positive integers n which is the size of the tree and k (k ≤ 500) which is the number of colours. Each of the following n - 1 lines contains two integers x and y describing an edge between them. We are sure that the given graph is a tree.
The summation of n in input is smaller than or equal to 200000.

Output

For each test case, output the maximum size of E1 ∩ E1 … ∩ Ek.

这个题没啥好想法，最初始的想法就是暴力，然后在几个小方法把需要遍历的东西进行精简，差不多就是：遍历+回溯，然后按一定顺序跑以避免重复。正在考虑等效点的存在能否简化计算。

本来拿Java写的，后来在优化上遇到一点问题，后来到网上搜了一下，看了看别人的做法，感觉很不错，仿照他们的用C++自己写了一个（长得有点一样）。回头用Java把自己之前的那个想法做出来吧。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string.h>
  4. #define LL long long
  5. #define N 100010
  6. using namespace std;
  7. const int MAX=1e6+10;
  8. const int matX = 105;
  9. const int mod = 100000000;
  10. int sizes[MAX];
  11. int ans=0;
  12. int n,k;
  13. int head[MAX];
  14. int all;
  15. class zqa {
  16.     public:
  17.         int u,v,next;
  18. };
  19. zqa q[MAX<<1];
  20. void add(int u,int v) {
  21.     q[all].u=u;
  22.     q[all].v=v;
  23.     q[all].next=head[u];
  24.     head[u]=all;
  25.     all++;
  26. }
  27. void zqazqa1(int u,int per) {
  28.     sizes[u]=1;
  29.     for(int i=head[u]; i!=-1; i=q[i].next) {
  30.         int v=q[i].v;
  31.         if(v==per) continue;
  32.         zqazqa1(v,u);
  33.         sizes[u]+=sizes[v];
  34.     }
  35.     if(sizes[u]>=k && n-sizes[u]>=k) ans++;
  36. }
  37. int main() {
  38.     int T;
  39.     scanf("%d",&T);
  40.     while(T--) {
  41.         all=0;
  42.         memset(head,-1,sizeof head);
  43.         memset(sizes,0,sizeof sizes);
  44.         ans=0;
  45.         scanf("%d %d",&n,&k);
  46.         for(int i=1; i<n; i++) {
  47.             int u,v;
  48.             scanf("%d %d",&u,&v);
  49.             add(u,v);
  50.             add(v,u);
  51.         }
  52.         zqazqa1(1,-1);
  53.         cout<<ans<<endl;
  54.     }
  55. }

E - Thickest Burger

https://vjudge.net/contest/354911#problem/E

ACM ICPC is launching a thick burger. The thickness (or the height) of a piece of club steak is A (1 ≤ A ≤ 100). The thickness (or the height) of a piece of chicken steak is B (1 ≤ B ≤ 100).
The chef allows to add just three pieces of meat into the burger and he does not allow to add three pieces of same type of meat. As a customer and a foodie, you want to know the maximum total thickness of a burger which you can get from the chef. Here we ignore the thickness of breads, vegetables and other seasonings.

Input

The first line is the number of test cases. For each test case, a line contains two positive integers A and B.

Output

For each test case, output a line containing the maximum total thickness of a burger.

水题一道，没啥可说的

  1. #include <iostream>
  2. #include<stdio.h>
  3. #include<math.h>
  4. using namespace std;
  5. int main()
  6. {
  7.     int n;
  8.     scanf("%d",&n);
  9.     while(n--)
  10.     {
  11.         int x,y;
  12.         cin>>x>>y;
  13.         int sum=x+x+y>y+y+x?x+x+y:y+y+x;
  14.         printf("%d\n",sum);
  15.     }
  16.     return 0;
  17. }

F - Relative atomic mass

https://vjudge.net/contest/354911#problem/F

Relative atomic mass is a dimensionless physical quantity, the ratio of the average mass of atoms of an element (from a single given sample or source) to 12of the mass of an atom of carbon-12 (known as the unified atomic mass unit).
You need to calculate the relative atomic mass of a molecule, which consists of one or several atoms. In this problem, you only need to process molecules which contain hydrogen atoms, oxygen atoms, and carbon atoms. These three types of atom are written as ’H’，’O’ and ’C’ repectively. For your information, the relative atomic mass of one hydrogen atom is 1, and the relative atomic mass of one oxygen atom is 16 and the relative atomic mass of one carbon atom is 12. A molecule is demonstrated as a string, of which each letter is for an atom. For example, a molecule ’HOH’ contains two hydrogen atoms and one oxygen atom, therefore its relative atomic mass is 18 = 2 * 1 + 16.

Input

The first line of input contains one integer N(N ≤ 10), the number of molecules. In the next N lines, the i-th line contains a string, describing the i-th molecule. The length of each string would not exceed 10.

Output

For each molecule, output its relative atomic mass.

又是水题一道。

  1. #include
  2. #include<stdio.h>
  3. #include<string.h>
  4. using namespace std;
  5. int main()
  6. {
  7.     int n;
  8.     scanf("%d",&n);
  9.     while(n--)
  10.     {
  11.         char zqa[11];
  12.         int sum=0;
  13.         scanf("%s",zqa);
  14.         int t=strlen(zqa);
  15.         int i;
  16.         for(i=0; i<t; i++)
  17.         {
  18.             if(zqa[i]=='H')sum+=1;
  19.             if(zqa[i]=='C')sum+=12;
  20.             if(zqa[i]=='O')sum+=16;
  21.         }
  22.         cout<<sum<<endl;
  23.     }
  24.     return 0;
  25. }

G - Recursive sequence

https://vjudge.net/contest/354911#problem/G

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b < 231231 as described above.

Output

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

这个题的题意是给了你一个递推公式，让你根据递推公式写出第算法-第一周 - 图8项是多少，然后要是真的去写递推的代码，绝对是超时了…..所以我一开始想的是根据其递推公式
算法-第一周 - 图9
求出它的通项公式来，然后在我算到
算法-第一周 - 图10
的时候，我感觉应该不是这么算（后来算出来了这个的通项公式…….极其丑陋，但把程序写出来后也的确是快的不得了），所以我感觉这个题应该不是这么做的。我后来去网上查找了一下别人的博客，他们用的是一个矩阵的计算，在这里我贴出来他们的帖子：

根据递推公式构造系数矩阵用于快速幂
https://blog.csdn.net/u012061345/article/details/52224623

矩阵快速幂和递推式构造常矩阵总结（感觉这个里头总结的最全）
https://blog.csdn.net/weixin_43872728/article/details/98113251

浅谈斐波那契数列——从递推到矩阵乘法
https://blog.csdn.net/ganjingxian/article/details/77160271

后来根据他们的原理，又写了一边，感觉他们的矩阵快速幂在这道题上，就使用一种比较巧妙的方法求出了隐式通项公式。

这个就是个模板题，背住背住（小本子记上），以后遇到直接套模板就行了

  1. import java.util.*;
  3. class M {
  4.     long[][] m = new long[7][7];
  5. };
  7. class p {
  8.     private long mod = 2147493647L;
  11.     private M zqa(M x, M y) {
  12.         M ret = new M();
  13.         for (int i = 0; i < 7; i++) {
  14.             for (int j = 0; j < 7; j++) {
  15.                 ret.m[i][j] = 0;
  16.                 for (int k = 0; k < 7; k++) {
  17.                     ret.m[i][j] = (x.m[i][k] * y.m[k][j] + ret.m[i][j]) % mod;
  18.                 }
  19.             }
  20.         }
  21.         return ret;
  22.     }
  24.     private M pow_M(M a, long zqazqa) {
  25.         M ret = new M();
  26.         Arrays.fill(ret.m[0],0);
  27.         Arrays.fill(ret.m[1],0);
  28.         Arrays.fill(ret.m[2],0);
  29.         Arrays.fill(ret.m[3],0);
  30.         Arrays.fill(ret.m[4],0);
  31.         Arrays.fill(ret.m[5],0);
  32.         Arrays.fill(ret.m[6],0);
  33.         for (int i = 0; i < 7; i++) ret.m[i][i] = 1;
  34.         while (zqazqa != 0) {
  35.             if ((zqazqa & 1) != 0) ret = zqa(ret, a);
  36.             a = zqa(a, a);
  37.             zqazqa >>= 1;
  38.         }
  39.         return ret;
  40.     }
  41.     p() {
  42.         Scanner scan=new Scanner(System.in);
  43.         int t=scan.nextInt();
  44.         while (t--!=0) {
  45.             long  m=scan.nextLong(),f1=scan.nextLong(), f2=scan.nextLong();
  46.             if (m == 1) System.out.println(f1);
  47.             else if (m == 2) System.out.println(f2);
  48.             else {
  49.                 M a=new M();
  50.                 Arrays.fill(a.m[0],0);
  51.                 Arrays.fill(a.m[1],0);
  52.                 Arrays.fill(a.m[2],0);
  53.                 Arrays.fill(a.m[3],0);
  54.                 Arrays.fill(a.m[4],0);
  55.                 Arrays.fill(a.m[5],0);
  56.                 Arrays.fill(a.m[6],0);
  57.                 a.m[0][0] = f2;
  58.                 a.m[1][0] = f1;
  59.                 a.m[2][0] = 1;
  60.                 a.m[3][0] = 2;
  61.                 a.m[4][0] = 4;
  62.                 a.m[5][0] = 8;
  63.                 a.m[6][0] = 16;
  64.                 M b =new M();
  65.                 b.m= new long[][]{
  66.                         {1, 2, 1, 4, 6, 4, 1},
  67.                         {1, 0, 0, 0, 0, 0, 0},
  68.                         {0, 0, 1, 0, 0, 0, 0},
  69.                         {0, 0, 1, 1, 0, 0, 0},
  70.                         {0, 0, 1, 2, 1, 0, 0},
  71.                         {0, 0, 1, 3, 3, 1, 0},
  72.                         {0, 0, 1, 4, 6, 4, 1}
  73.                 };
  74.                 a = zqa(pow_M(b, m - 2) , a);
  75.                 System.out.println(a.m[0][0]);
  76.             }
  77.         }
  78.     }
  79. }
  80. public class Main {
  81.     public static void main(String[] args) {
  82.         new p();
  83.     }
  84. }

H - Counting Cliques

https://vjudge.net/contest/354911#problem/H

A clique is a complete graph, in which there is an edge between every pair of the vertices. Given a graph with N vertices and M edges, your task is to count the number of cliques with a specific size S in the graph.

Input

The first line is the number of test cases. For each test case, the first line contains 3 integers N,M and S (N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10), each of the following M lines contains 2 integers u and v (1 ≤ u < v ≤ N), which means there is an edge between vertices u and v. It is guaranteed that the maximum degree of the vertices is no larger than 20.

Output

For each test case, output the number of cliques with size S in the graph.

题目的意思不难，求初始图的完全子图，就是个遍历和栈，然后就是跑就可以了。

这个题让我无比痛苦，谁能想到这个题用Java跑就过不了，用C++重写了一遍跑就可以呢

先贴Java代码

  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  5. class Point{
  6.     boolean used=false;
  7.     ArrayList<Integer> target= new ArrayList<>();
  8. }
  9. class p{
  10.     private int all;
  11.     private Stack<Integer> member;
  12.     private Point[] sign;
  13.     private void search(int position,int pointnum){
  14.         for(Integer i:member){
  15.                 if(i==position)continue;
  16.                 if(sign[position].target.indexOf(i)==-1)return;
  17.         }
  18.         if(pointnum==1){
  19.             all++;
  20.         }else {
  21.             for(Integer i:sign[position].target){
  22.                 if(!sign[i].used){
  23.                     if(member.peek()<i&&member.indexOf(i)==-1){
  24.                         member.push(i);
  25.                         search(i,pointnum-1);
  26.                         member.pop();
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     p() {
  33.         Scanner scan = new Scanner(System.in);
  34.         int T;
  35.         T=scan.nextInt();
  36.         while(T--!=0) {
  37.             this.member= new Stack<>();
  38.             this.all=0;
  39.             int point = scan.nextInt();
  40.             int line = scan.nextInt();
  41.             int num = scan.nextInt();
  42.             //数据初始化
  43.             sign=new Point[point +1];
  44.             for(int k = 0; k< line; k++){
  45.                 int n=scan.nextInt();
  46.                 int m=scan.nextInt();
  47.                 if(sign[n]==null)sign[n]=new Point();
  48.                 if(sign[m]==null)sign[m]=new Point();
  49.                 sign[n].target.add(m);
  50.                 sign[m].target.add(n);
  51.             }
  52.             for(int k = 1; k<= point - num+1; k++){
  53.                 if(sign[k].target.size()<num-1)continue;
  54.                 member.push(k);
  55.                 search(k, num);
  56.                 member.pop();
  57.                 sign[k].used=true;
  58.             }
  59.             System.out.println(all);
  60.         }
  61.     }
  62. }
  63. public class Main {
  64.     public static void main(String[] args) {
  65.         new p();
  66.     }
  67. }

再贴C++代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 1e6+10;
  7. typedef long long LL;
  8. int head[110], cnt;
  9. struct node
  10. {
  11.     bool uesd;
  12.     int to, next;
  13. } zqa1[N];
  14. int w[105][105], zqazqa[105], c[110], c1[110], val[105];
  15. int ans;
  16. void init()
  17. {
  18.     memset(head,-1,sizeof(head));
  19.     memset(w,0,sizeof(w));
  20.     memset(c,0,sizeof(c));
  21.     cnt=0,ans=0;
  22.     return ;
  23. }
  24. void add(int u,int v)
  25. {
  26.     zqa1[cnt].to=v,zqa1[cnt].next=head[u];
  27.     head[u]=cnt++;
  28.     return ;
  29. }
  30. int zqa[110];
  31. void dfs(int u,int d,int s,int n)
  32. {
  33.     for(int i=1; i<d; i++)
  34.         if(w[zqa[i]][u]==0) return ;
  35.     if(d==s)
  36.     {
  37.         ans++;
  38.         return ;
  39.     }
  40.     for(int i=head[u]; i!=-1; i=zqa1[i].next)
  41.     {
  42.         int v=zqa1[i].to;
  43.         if(c[v]) continue;
  44.         zqa[d+1]=v;
  45.         dfs(v,d+1,s,n);
  46.     }
  47.     return ;
  48. }
  49. int main()
  50. {
  51.     int t;
  52.     scanf("%d", &t);
  53.     while(t--)
  54.     {
  55.         int n, m, s;
  56.         scanf("%d %d %d", &n, &m, &s);
  57.         init();
  58.         for(int i=0; i<m; i++)
  59.         {
  60.             int x, y;
  61.             scanf("%d %d", &x, &y);
  62.             if(w[x][y]==0)
  63.             {
  64.                 w[x][y]=1,w[y][x]=1;
  65.                 if(x>y)swap(x,y);
  66.                 add(x,y);
  67.             }
  68.         }
  69.         for(int i=1; i<=n; i++)
  70.         {
  71.             zqa[1]=i,c[i]=1;
  72.             dfs(i,1,s,n);
  73.         }
  74.         printf("%d\n",ans);
  75.     }
  76.     return 0;
  77. }