//Varun
#include "bits/stdc++.h"
using namespace std;
#define si(x) scanf("%d",&x)
#define sll(x) scanf("%I64d",&x)
#define pb push_back
#define gcd(a,b) __gcd(a,b)
#define F first
#define S second
#define SETBITS(x) __builtin_popcount(x)
#define ALL(x) (x).begin(),(x).end()
#define REP(a,b) for(int i=a;i<b;i++)
#define REP2(a,b,c) for(int i=a;i<b;i+=c)
#define fastscan ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug(x) cerr<<#x<<" is "<<x<<endl
#define INF INT_MAX
#define N_INF INT_MIN
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const ll mod = 1e9+7;
const ll maxn = 2e5+5;
std::vector<ll>g[maxn];
ll dfs_par[maxn];//for cycle detection
ll cyc_par[maxn];//to store root of each cycle
ll vis[maxn];//1st dfs
pll in[maxn], out[maxn];
ll dfn[maxn];
ll num = 0;
pll merge(pll a, pll b, ll x, ll y){
// if(x == 8){
// cout << y << b.F << b.S << "\n";
// }
if(cyc_par[x] == cyc_par[y]){
return {a.F, a.S+b.F};
}
else{
return {a.F+b.F, a.S+b.S};
}
}
pll unmerge(pll a, pll b, ll x, ll y){
if(cyc_par[x] == cyc_par[y]){
a.S -= b.F;
}
else{
a.F -= b.F, a.S -= b.S;
}
return a;
}
void dfs(ll start, ll pre){
//trace(start, pre);
if(vis[start] == 0){
dfn[start] = num++;
}
vis[start]++;
for(ll i = 0; i < g[start].size(); ++i){
ll child = g[start][i];
if(child == pre)continue;
if(vis[child] >= 2)continue;
else if(vis[child] == 0){
dfs_par[child] = start;
dfs(child, start);
}
else{
ll dum=start;
while(cyc_par[dum] != child){
cyc_par[dum] = child;
dum = dfs_par[dum];
}
}
}
vis[start]++;
}
void dfs_in(ll start, ll pre){
//trace(start, pre);
vis[start]++;
in[start] = {1, 0};
ll back = -1;
for(auto child : g[start]){
if(child == pre)continue;
if(vis[child] == 0){
dfs_in(child, start);
in[start] = merge(in[start], in[child], start, child);
}
else if(vis[child] == 1){
back = child;
}
}
if(back != -1){
in[back] = merge(in[back], in[start], back, start);
}
vis[start]++;
}
void dfs_out(ll start, ll pre){
vis[start]++;
out[start] = {1, 0};
if(pre != 0){
out[start] = merge(out[start], out[pre], start, pre);
for(auto sibling : g[pre]){
ll count = 0;
if(sibling == start)continue;// or sibling == dfs_par[pre])continue;
if(cyc_par[start] == cyc_par[pre])++count;
if(cyc_par[pre] == cyc_par[sibling])++count;
if(count == 2)continue;
if(dfs_par[sibling] == pre){
if(count){
out[start] = merge(out[start], {0, in[sibling].F}, start, 0);
}
else
out[start] = merge(out[start], in[sibling], start, sibling);
}
}
}
for(auto child : g[start]){
if(child == pre)continue;
if(dfn[child] < dfn[start]){
out[start] = merge(out[start], out[child], start, child);
break;
}
}
for(auto child : g[start]){
if(child == pre)continue;
if(vis[child] == 0){
dfs_out(child, start);
}
}
vis[start]++;
}
ll ans(ll a, ll b){
if(dfs_par[a] == b){
swap(a, b);
}
pll x = in[b];
pll y = {0, 0};
for(auto sibling : g[a]){
ll count = 0;
if(sibling == b or sibling == dfs_par[a])continue;
//if(dfs_par[sibling] == a){
if(dfn[sibling] > dfn[a] and dfn[sibling] != dfn[b]){
if(cyc_par[b] == cyc_par[a])count++;
if(cyc_par[a] == cyc_par[sibling])++count;
if(count == 2)continue;
if(count == 1)
y = merge(y, {0, in[sibling].F}, a, 0);
else
y = merge(y, in[sibling], a, sibling);
}
}
//pll x = in[b];
//pll y = unmerge(in[a], in[b], a, b);
//y = unmerge(y, {1, 0}, a, 0);
y = merge(y, out[a], a, b);
// if(b == 8)
// trace(y.F, y.S);
// if(cyc_par[a] == cyc_par[b]){
// return 1LL*x.F*y.F;
// }
// else{
return x.F*y.F + x.S*y.F + x.F*y.S;
//}
}
std::vector<pll> edges;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fastscan;
ll t;
cin >> t;
while(t--){
ll n, m;
num = 0;
cin >> n >> m;
edges.clear();
for(ll i = 0; i <= n; ++i){
g[i].clear();
dfs_par[i] = 0;
cyc_par[i] = i;
vis[i] = 0;
}
for(ll i = 0; i < m; ++i){
ll u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
edges.pb({u, v});
}
vis[0] = 1;
for(ll i = 1; i <= n; ++i){
if(!vis[i]){
dfs(i, 0);
dfs_par[i] = 0;
// for(int j = 1; j <= n; ++j){
// cout << cyc_par[j] <<'\n';
// }
// cout << '\n';
for(int i = 0; i <= n; ++i)vis[i] = 0;
vis[0] = 1;
dfs_in(i, 0);
// for(int j = 1; j <= n; ++j){
// cout << in[j].F << " " << in[j].S <<'\n';
// }
// cout <<"\n\n\n\n";
for(int i = 0; i <= n; ++i)vis[i] = 0;
vis[0] = 1;
dfs_out(i, 0);
// for(int j = 1; j <= n; ++j){
// cout << out[j].F << " " << out[j].S <<'\n';
// }
}
}
//trace(out[8].F, out[8].S);
// for(int i = 1; i <= n; ++i){
// cout << dfn[i] << " ";
// }
//cout << "\n";
for(ll i = 0; i < edges.size(); ++i){
cout << ans(edges[i].F, edges[i].S) << "\n";
}
}
return 0;
}
/*
Input
1
14 14
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
6 9
8 10
10 11
11 12
12 13
13 14
*/
/*
Expected Output
1
1
2
2
11
14
7
2
25
9
24
21
16
9
*/
Ly9WYXJ1bgojaW5jbHVkZSAiYml0cy9zdGRjKysuaCIKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBzaSh4KSBzY2FuZigiJWQiLCZ4KQojZGVmaW5lIHNsbCh4KSBzY2FuZigiJUk2NGQiLCZ4KQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGdjZChhLGIpIF9fZ2NkKGEsYikKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBTRVRCSVRTKHgpIF9fYnVpbHRpbl9wb3Bjb3VudCh4KQojZGVmaW5lIEFMTCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBSRVAoYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQojZGVmaW5lIFJFUDIoYSxiLGMpIGZvcihpbnQgaT1hO2k8YjtpKz1jKSAgIAojZGVmaW5lIGZhc3RzY2FuIGlvczo6c3luY193aXRoX3N0ZGlvKDApLGNpbi50aWUoMCksY291dC50aWUoMCkKI2RlZmluZSBkZWJ1Zyh4KSBjZXJyPDwjeDw8IiBpcyAiPDx4PDxlbmRsCiNkZWZpbmUgSU5GIElOVF9NQVgKI2RlZmluZSBOX0lORiBJTlRfTUlOCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gcGk7CnR5cGVkZWYgcGFpcjxsbCxsbD4gcGxsOwogICAgICAgIAojZGVmaW5lIFRSQUNFCgojaWZkZWYgVFJBQ0UKI2RlZmluZSB0cmFjZSguLi4pIF9fZigjX19WQV9BUkdTX18sIF9fVkFfQVJHU19fKQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMT4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZSwgQXJnMSYmIGFyZzEpewogIGNlcnIgPDwgbmFtZSA8PCAiIDogIiA8PCBhcmcxIDw8IHN0ZDo6ZW5kbDsKfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMSwgdHlwZW5hbWUuLi4gQXJncz4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZXMsIEFyZzEmJiBhcmcxLCBBcmdzJiYuLi4gYXJncyl7CiAgY29uc3QgY2hhciogY29tbWEgPSBzdHJjaHIobmFtZXMgKyAxLCAnLCcpO2NlcnIud3JpdGUobmFtZXMsIGNvbW1hIC0gbmFtZXMpIDw8ICIgOiAiIDw8IGFyZzE8PCIgfCAiO19fZihjb21tYSsxLCBhcmdzLi4uKTsKfQojZWxzZQojZGVmaW5lIHRyYWNlKC4uLikKI2VuZGlmCgpjb25zdCBsbCBtb2QgPSAxZTkrNzsKY29uc3QgbGwgbWF4biA9IDJlNSs1OwoKc3RkOjp2ZWN0b3I8bGw+Z1ttYXhuXTsKCmxsIGRmc19wYXJbbWF4bl07Ly9mb3IgY3ljbGUgZGV0ZWN0aW9uCmxsIGN5Y19wYXJbbWF4bl07Ly90byBzdG9yZSByb290IG9mIGVhY2ggY3ljbGUKbGwgdmlzW21heG5dOy8vMXN0IGRmcwpwbGwgaW5bbWF4bl0sIG91dFttYXhuXTsKbGwgZGZuW21heG5dOwpsbCBudW0gPSAwOwoKcGxsIG1lcmdlKHBsbCBhLCBwbGwgYiwgbGwgeCwgbGwgeSl7CiAgICAvLyBpZih4ID09IDgpewogICAgLy8gIGNvdXQgPDwgeSA8PCBiLkYgPDwgYi5TIDw8ICJcbiI7CiAgICAvLyB9CiAgICBpZihjeWNfcGFyW3hdID09IGN5Y19wYXJbeV0pewogICAgICAgIHJldHVybiB7YS5GLCBhLlMrYi5GfTsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgcmV0dXJuIHthLkYrYi5GLCBhLlMrYi5TfTsKICAgIH0KfQoKcGxsIHVubWVyZ2UocGxsIGEsIHBsbCBiLCBsbCB4LCBsbCB5KXsKICAgIGlmKGN5Y19wYXJbeF0gPT0gY3ljX3Bhclt5XSl7CiAgICAgICAgYS5TIC09IGIuRjsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgYS5GIC09IGIuRiwgYS5TIC09IGIuUzsKICAgIH0KICAgIHJldHVybiBhOwp9Cgp2b2lkIGRmcyhsbCBzdGFydCwgbGwgcHJlKXsKICAgIC8vdHJhY2Uoc3RhcnQsIHByZSk7CiAgICBpZih2aXNbc3RhcnRdID09IDApewogICAgICAgIGRmbltzdGFydF0gPSBudW0rKzsKICAgIH0KICAgIHZpc1tzdGFydF0rKzsKICAgIGZvcihsbCBpID0gMDsgaSA8IGdbc3RhcnRdLnNpemUoKTsgKytpKXsKICAgICAgICBsbCBjaGlsZCA9IGdbc3RhcnRdW2ldOwogICAgICAgIGlmKGNoaWxkID09IHByZSljb250aW51ZTsKCiAgICAgICAgaWYodmlzW2NoaWxkXSA+PSAyKWNvbnRpbnVlOwoKICAgICAgICBlbHNlIGlmKHZpc1tjaGlsZF0gPT0gMCl7CiAgICAgICAgICAgIGRmc19wYXJbY2hpbGRdID0gc3RhcnQ7CiAgICAgICAgICAgICAgICBkZnMoY2hpbGQsIHN0YXJ0KTsKICAgICAgICB9CgogICAgICAgIGVsc2V7CiAgICAgICAgICAgIGxsIGR1bT1zdGFydDsKICAgICAgICAgICAgd2hpbGUoY3ljX3BhcltkdW1dICE9IGNoaWxkKXsKICAgICAgICAgICAgICAgIGN5Y19wYXJbZHVtXSA9IGNoaWxkOwogICAgICAgICAgICAgICAgZHVtID0gZGZzX3BhcltkdW1dOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgdmlzW3N0YXJ0XSsrOwp9Cgp2b2lkIGRmc19pbihsbCBzdGFydCwgbGwgcHJlKXsKICAgIC8vdHJhY2Uoc3RhcnQsIHByZSk7CiAgICB2aXNbc3RhcnRdKys7CiAgICBpbltzdGFydF0gPSB7MSwgMH07CgogICAgbGwgYmFjayA9IC0xOwogICAgZm9yKGF1dG8gY2hpbGQgOiBnW3N0YXJ0XSl7CiAgICAgICAgaWYoY2hpbGQgPT0gcHJlKWNvbnRpbnVlOwogICAgICAgIGlmKHZpc1tjaGlsZF0gPT0gMCl7CiAgICAgICAgICAgIGRmc19pbihjaGlsZCwgc3RhcnQpOwogICAgICAgICAgICBpbltzdGFydF0gPSBtZXJnZShpbltzdGFydF0sIGluW2NoaWxkXSwgc3RhcnQsIGNoaWxkKTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZih2aXNbY2hpbGRdID09IDEpewogICAgICAgICAgICBiYWNrID0gY2hpbGQ7CiAgICAgICAgfQogICAgfQogICAgaWYoYmFjayAhPSAtMSl7CiAgICAgICAgaW5bYmFja10gPSBtZXJnZShpbltiYWNrXSwgaW5bc3RhcnRdLCBiYWNrLCBzdGFydCk7CiAgICB9CiAgICB2aXNbc3RhcnRdKys7Cn0KCnZvaWQgZGZzX291dChsbCBzdGFydCwgbGwgcHJlKXsKICAgIHZpc1tzdGFydF0rKzsKCiAgICBvdXRbc3RhcnRdID0gezEsIDB9OwoKCiAgICBpZihwcmUgIT0gMCl7CiAgICAgICAgb3V0W3N0YXJ0XSA9IG1lcmdlKG91dFtzdGFydF0sIG91dFtwcmVdLCBzdGFydCwgcHJlKTsKICAgICAgICBmb3IoYXV0byBzaWJsaW5nIDogZ1twcmVdKXsKICAgICAgICAgICAgbGwgY291bnQgPSAwOwoKICAgICAgICAgICAgaWYoc2libGluZyA9PSBzdGFydCljb250aW51ZTsvLyBvciBzaWJsaW5nID09IGRmc19wYXJbcHJlXSljb250aW51ZTsKCiAgICAgICAgICAgIGlmKGN5Y19wYXJbc3RhcnRdID09IGN5Y19wYXJbcHJlXSkrK2NvdW50OwogICAgICAgICAgICBpZihjeWNfcGFyW3ByZV0gPT0gY3ljX3BhcltzaWJsaW5nXSkrK2NvdW50OwoKICAgICAgICAgICAgaWYoY291bnQgPT0gMiljb250aW51ZTsKCiAgICAgICAgICAgIGlmKGRmc19wYXJbc2libGluZ10gPT0gcHJlKXsKICAgICAgICAgICAgICAgIGlmKGNvdW50KXsKICAgICAgICAgICAgICAgICAgICBvdXRbc3RhcnRdID0gbWVyZ2Uob3V0W3N0YXJ0XSwgezAsIGluW3NpYmxpbmddLkZ9LCBzdGFydCwgMCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgb3V0W3N0YXJ0XSA9IG1lcmdlKG91dFtzdGFydF0sIGluW3NpYmxpbmddLCBzdGFydCwgc2libGluZyk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgZm9yKGF1dG8gY2hpbGQgOiBnW3N0YXJ0XSl7CiAgICAgICAgaWYoY2hpbGQgPT0gcHJlKWNvbnRpbnVlOwogICAgICAgIGlmKGRmbltjaGlsZF0gPCBkZm5bc3RhcnRdKXsKICAgICAgICAgICAgb3V0W3N0YXJ0XSA9IG1lcmdlKG91dFtzdGFydF0sIG91dFtjaGlsZF0sIHN0YXJ0LCBjaGlsZCk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KCiAgICBmb3IoYXV0byBjaGlsZCA6IGdbc3RhcnRdKXsKICAgICAgICBpZihjaGlsZCA9PSBwcmUpY29udGludWU7CiAgICAgICAgaWYodmlzW2NoaWxkXSA9PSAwKXsKICAgICAgICAgICAgZGZzX291dChjaGlsZCwgc3RhcnQpOwogICAgICAgIH0KICAgIH0KICAgIHZpc1tzdGFydF0rKzsKfQoKbGwgYW5zKGxsIGEsIGxsIGIpewogICAgaWYoZGZzX3BhclthXSA9PSBiKXsKICAgICAgICBzd2FwKGEsIGIpOwogICAgfQoKICAgIHBsbCB4ID0gaW5bYl07CiAgICBwbGwgeSA9IHswLCAwfTsKCiAgICBmb3IoYXV0byBzaWJsaW5nIDogZ1thXSl7CiAgICAgICAgICAgIGxsIGNvdW50ID0gMDsKCiAgICAgICAgICAgIGlmKHNpYmxpbmcgPT0gYiBvciBzaWJsaW5nID09IGRmc19wYXJbYV0pY29udGludWU7CgogICAgICAgICAgICAvL2lmKGRmc19wYXJbc2libGluZ10gPT0gYSl7CiAgICAgICAgICAgIGlmKGRmbltzaWJsaW5nXSA+IGRmblthXSBhbmQgZGZuW3NpYmxpbmddICE9IGRmbltiXSl7CiAgICAgICAgICAgICAgICAgICAgICAgaWYoY3ljX3BhcltiXSA9PSBjeWNfcGFyW2FdKWNvdW50Kys7CiAgICAgICAgICAgICAgICAgICAgICAgaWYoY3ljX3BhclthXSA9PSBjeWNfcGFyW3NpYmxpbmddKSsrY291bnQ7CiAgICAgICAgICAgICAgICAgICAgICAgaWYoY291bnQgPT0gMiljb250aW51ZTsKICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgaWYoY291bnQgPT0gMSkKICAgICAgICAgICAgICAgICAgICAgICAgIHkgPSBtZXJnZSh5LCB7MCwgaW5bc2libGluZ10uRn0sIGEsIDApOwogICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgeSA9IG1lcmdlKHksIGluW3NpYmxpbmddLCBhLCBzaWJsaW5nKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICB9CgogICAgLy9wbGwgeCA9IGluW2JdOwogICAgLy9wbGwgeSA9IHVubWVyZ2UoaW5bYV0sIGluW2JdLCBhLCBiKTsKICAgIC8veSA9IHVubWVyZ2UoeSwgezEsIDB9LCBhLCAwKTsKICAgIHkgPSBtZXJnZSh5LCBvdXRbYV0sIGEsIGIpOwogICAgLy8gaWYoYiA9PSA4KQogICAgICAgIC8vICB0cmFjZSh5LkYsIHkuUyk7CiAgICAvLyBpZihjeWNfcGFyW2FdID09IGN5Y19wYXJbYl0pewogICAgLy8gIHJldHVybiAxTEwqeC5GKnkuRjsKICAgIC8vIH0KICAgIC8vIGVsc2V7CiAgICAgICAgcmV0dXJuIHguRip5LkYgKyB4LlMqeS5GICsgeC5GKnkuUzsKICAgIC8vfQp9CgpzdGQ6OnZlY3RvcjxwbGw+IGVkZ2VzOwoKaW50IG1haW4oKQp7CiAgICAjaWZuZGVmIE9OTElORV9KVURHRQogICAgICAgIGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwogICAgICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICAjZW5kaWYKCiAgICBmYXN0c2NhbjsKCgogICAgbGwgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUodC0tKXsKICAgICAgICBsbCBuLCBtOwogICAgICAgIG51bSA9IDA7CiAgICAgICAgY2luID4+IG4gPj4gbTsKICAgICAgICBlZGdlcy5jbGVhcigpOwogICAgICAgIGZvcihsbCBpID0gMDsgaSA8PSBuOyArK2kpewogICAgICAgICAgICBnW2ldLmNsZWFyKCk7CiAgICAgICAgICAgIGRmc19wYXJbaV0gPSAwOwogICAgICAgICAgICBjeWNfcGFyW2ldID0gaTsKICAgICAgICAgICAgdmlzW2ldID0gMDsKICAgICAgICB9CgoKCiAgICAgICAgZm9yKGxsIGkgPSAwOyBpIDwgbTsgKytpKXsKICAgICAgICAgICAgbGwgdSwgdjsKICAgICAgICAgICAgY2luID4+IHUgPj4gdjsKICAgICAgICAgICAgZ1t1XS5wYih2KTsKICAgICAgICAgICAgZ1t2XS5wYih1KTsKICAgICAgICAgICAgZWRnZXMucGIoe3UsIHZ9KTsKICAgICAgICB9CiAgICAgICAgdmlzWzBdID0gMTsKICAgICAgICBmb3IobGwgaSA9IDE7IGkgPD0gbjsgKytpKXsKICAgICAgICAgICAgaWYoIXZpc1tpXSl7CiAgICAgICAgICAgICAgICBkZnMoaSwgMCk7CiAgICAgICAgICAgICAgICBkZnNfcGFyW2ldID0gMDsKICAgICAgICAgICAgICAgICAvLyBmb3IoaW50IGogPSAxOyBqIDw9IG47ICsrail7CiAgICAgICAgICAgICAgICAgLy8gICAgIGNvdXQgPDwgY3ljX3BhcltqXSA8PCdcbic7CiAgICAgICAgICAgICAgICAgLy8gfQogICAgICAgICAgICAgICAgIC8vIGNvdXQgPDwgJ1xuJzsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IG47ICsraSl2aXNbaV0gPSAwOwogICAgICAgICAgICAgICAgICAgIHZpc1swXSA9IDE7CiAgICAgICAgICAgICAgICBkZnNfaW4oaSwgMCk7CiAgICAgICAgICAgICAgICAgLy8gZm9yKGludCBqID0gMTsgaiA8PSBuOyArK2opewogICAgICAgICAgICAgICAgIC8vICAgICBjb3V0IDw8IGluW2pdLkYgPDwgIiAiIDw8IGluW2pdLlMgPDwnXG4nOwogICAgICAgICAgICAgICAgIC8vIH0KICAgICAgICAgICAgICAgICAvLyBjb3V0IDw8IlxuXG5cblxuIjsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IG47ICsraSl2aXNbaV0gPSAwOwogICAgICAgICAgICAgICAgICAgIHZpc1swXSA9IDE7CiAgICAgICAgICAgICAgICBkZnNfb3V0KGksIDApOwogICAgICAgICAgICAgICAgIC8vIGZvcihpbnQgaiA9IDE7IGogPD0gbjsgKytqKXsKICAgICAgICAgICAgICAgICAvLyAgICAgY291dCA8PCBvdXRbal0uRiA8PCAiICIgPDwgb3V0W2pdLlMgPDwnXG4nOwogICAgICAgICAgICAgICAgIC8vIH0KICAgICAgICAgICAgfSAgICAgICAgICAgCiAgICAgICAgfQoKICAgICAgICAvL3RyYWNlKG91dFs4XS5GLCBvdXRbOF0uUyk7ICAgICAgICAgICAgICAgIAogICAgICAgIAogICAgICAgIC8vIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKXsKICAgICAgICAvLyAgICAgICBjb3V0IDw8IGRmbltpXSA8PCAiICI7CiAgICAgICAgLy8gfQogICAgICAgIC8vY291dCA8PCAiXG4iOwoKICAgICAgICBmb3IobGwgaSA9IDA7IGkgPCBlZGdlcy5zaXplKCk7ICsraSl7CiAgICAgICAgICAgIGNvdXQgPDwgYW5zKGVkZ2VzW2ldLkYsIGVkZ2VzW2ldLlMpIDw8ICJcbiI7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0KCi8qIApJbnB1dAoxCjE0IDE0CjEgMgoyIDMKMyA0CjQgMQo0IDUKNSA2CjYgNwo3IDUKNiA4CjYgOQo4IDEwCjEwIDExCjExIDEyCjEyIDEzCjEzIDE0CiovCgovKgpFeHBlY3RlZCBPdXRwdXQKMQoxCjIKMgoxMQoxNAo3CjIKMjUKOQoyNAoyMQoxNgo5Ciov