

colorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 169 Accepted Submission(s): 21 Problem Description You are given a directed graph, which is constructed as follows: + Pick an connected undirected graph with exactly n vertices and n edges. The vertices are numbered 1 through n. + Convert each undirected edge into a directed edge, satisfying each vertice's outdegree equals 1. Also you're given m different colors to color the vertices. Your task is to calculate the number of different colored graphs that can be made. Two colored graphs A and B are considered the same if and only if there exists a mapping P satisfying the following constraints: + Vertice u in graph A has the same color as vertice P(u) in graph B. + For any two different vertices u and v in graph A, P(u) and P(v) are different vertices in graph B. + For any directed edge u > v in graph A, there exists a corresponding directed edge P(u) > P(v) in graph B. Print the answer module 10^9 + 7. Input The first line contains a number T(1 <= T <= 10), denoting the number of testcases. For each testcase, the first line contains two spaceseperated integers n and m(3 <= n <= 10^5, 1 <= m <= 10^9), representing the number of vertices in the graph and the number of colors you have. Then, n lines follow. The ith of them contains an integer f_i, denoting a directed edge from vertice i to vertice f_i in the given graph.(1 <= f_i <= n, f_i != i) Output For each testcase, print a line containing the answer. Sample Input
Sample Output
Author 学军中学 Source  
