一开始，我想的是建一个矩阵，然后尽量多的乘，做快速幂，做到后面会自然稳定，但是没去实现，考虑到一个问题，每个点的出度不一样，所以不是简单的求和，而且后面改边又要做矩阵快速幂，会tle。
后来学了发高斯消元，这道题充分利用了高斯消元的性质，因为改边只会影响最后一列，所以改一次边，就再在矩阵后面添加一列，增光。
最后，只需要枚举到底选取哪一列能使得答案最优就行了。

//
//  Created by Running Photon on 2016-03-06
//  Copyright (c) 2015 Running Photon. All rights reserved.
//
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <sstream>
#include <set>
#include <vector>
#include <stack>
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x,begin())
#define ll long long
#define CLR(x) memset(x, 0, sizeof x)
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 1e3 + 10;
const int maxv = 1e2 + 10;
const double eps = 1e-9;double A[maxv][305];
int Gauss(int edu, int var) {int row, col;for(row = 0, col = 0; row < edu && col < var; row++, col++) {int maxrow = row;for(int i = row + 1; i < edu; i++) {if(fabs(A[maxrow][col]) < fabs(A[i][col])) maxrow = i;}if(fabs(A[maxrow][col]) < eps) return 0;if(maxrow != row) {for(int j = col; j < var; j++) {swap(A[maxrow][j], A[row][j]);}}for(int j = col + 1; j < var; j++) {A[row][j] /= A[row][col];}A[row][col] = 1;for(int i = row + 1; i < edu; i++) {for(int j = col + 1; j < var; j++) {A[i][j] -= A[row][j] * A[i][col];}A[i][col] = 0;}}return 1;
}
double out[maxv];int G[maxv][maxv];
int ID[maxv];
int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
//  ios_base::sync_with_stdio(0);int T;scanf("%d", &T);while(T--) {int n, m;scanf("%d%d", &n, &m);CLR(out);CLR(G);CLR(A);for(int i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v);G[u][v]++;out[u] += 1;}for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(i != j && G[j][i]) {A[i][j] = 1.0 / out[j];}}A[i][i] = -1;}for(int i = 0; i <= n; i++)A[n-1][i] = 1;int cnt = 1;for(int i = 0; i < n - 1; i++) {if(!G[n - 1][i]) {for(int j = 0; j < n; j++) {if(G[n - 1][j]) {A[j][n + cnt] = 1.0 / (out[n - 1] + 1);}else A[j][n + cnt] = 0;}A[i][n + cnt] = 1.0 / (out[n - 1] + 1);A[n - 1][n + cnt] = 1;ID[cnt++] = i;}}if(!Gauss(n, n + cnt)) {puts("INF");continue;}int ans = -1;double mmax = A[n - 1][n] / A[n - 1][n - 1];for(int i = 1; i < cnt; i++) {if(A[n - 1][n] / A[n - 1][n + i] > mmax + eps) {mmax = A[n - 1][n] / A[n - 1][n + i];ans = ID[i];}}printf("1 %d\n", ans);}return 0;
}