CSES :: Graph Algorithms :: Round Trip

Problem : Please find the problem here.

Explanation : We need to find out the path in the graph where start and end node is the same (a cycle).
This can be easily checked with simple Graph Traveral, check if any of the node's children node, during traversal, is already visited by some other parent.

Code : Used DFS to check cycles in the graph and backtracking the path using the nodes parent array maintained over traversal.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, int pu, vector<int> (&adj)[mxN], vector<int> &visited, vector<int> &parent) {
    visited[u] = 1;
    parent[u] = pu;

    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, u, adj, visited, parent);
        } else {
            if (v == pu) {
                continue;
            }
            else {
                int u2 = u;
                vector<int> ans;
                while (u^v) {
                    ans.emplace_back(u);
                    u = parent[u];
                }

                ans.push_back(v);
                ans.push_back(u2);

                cout << ans.size() << '\n';
                for (auto a : ans) {
                    cout << a+1 << ' ';
                }
                exit(0);
            }

        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> adj[mxN], visited(n, 0), parent(n, 0);


    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v; u--, v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) DFS(i, -1, adj, visited, parent);
    }

    cout << "IMPOSSIBLE";

    return 0;
}

CSES :: Graph Algorithms :: Building Roads

Problem : Please find the problem here.

Explanation : Given a graph structure, number of roads here is basically the minimum edges required to make this graph connected. This is intern equal to number of connected components in the graph.
Save any one node from each connected components and print the path in between those nodes.

Code : Used DFS to find connected components.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, map<int, set<int>> &adj, vector<bool> &vis) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            DFS(v, adj, vis);
        }
    }
}

vector<int> countRoads(int n, map<int, set<int>> &adj, vector<bool> &vis) {
    vector<int> roads;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(i, adj, vis);
            roads.emplace_back(i);
        }
    }

    return roads;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int n, m, a, b;
    cin >> n >> m;

    map<int, set<int>> adj;
    for (int i = 0; i < m; i++) {
        cin >> a >> b; a--, b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    vector<bool> vis(n, 0);
    vector<int> result = countRoads(n, adj, vis);

    cout << result.size()-1 << '\n';
    for (int i = 1; i < (int)result.size(); i++) {
        cout << result[0]+1 << ' ' << result[i]+1 << '\n';
    }
    return 0;
}

CSES :: Tree Algorithms :: Subordinates

Problem : Please find the problem here.

Explanation : Company's employee hierarchy can be intutively mapped as tree structure and for each employee, the subordinate count is the sum of subordinates count of all their direct subordinates.

Code : Used DFS to traverse the tree starting from the node 0. This calculates the subordinates for each employee by summing counts recursively.

Time Complexity : O(N), where n is the number of nodes in the tree.

#include <bits/stdc++.h>

using namespace std;

void DFS(int node, int parent, vector<int> &subordinates, vector<vector<int>> &adj) {
    subordinates[node] = 1;

    for (int next : adj[node]) {
        DFS(next, node, subordinates, adj);
        subordinates[node] += subordinates[next];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> subordinates(n);

    // relation data for employee 1 to n; 0th is boss.
    for (int i = 1; i < n; i++) {
        cin >> x; x--;
        adj[x].emplace_back(i);
    }

    DFS(0, -1, subordinates, adj);

    for (int c : subordinates) {
        cout << c-1 << ' ';
    }
    return 0;
}

CSES :: Graph Algorithms :: Counting Rooms

Problem : Please find the problem here.

Explanation : considering the given structure as graph, with each '.' character being an edge between ith and jth node, the number of rooms is equal to number of connected components in the graph.

Code : Used DFS to count number of connected components.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e3;
const int di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1};
int n, m;
string adj[mxN];

bool isValid(int i, int j) {
    return (i >= 0 && j >= 0 && i < n && j < m && adj[i][j]=='.');
}

void DFS(int i, int j) {
    adj[i][j] = '#';

    for (int k = 0; k < 4; k++) {
        if (isValid(i + di[k], j + dj[k])) {
            DFS(i + di[k], j + dj[k]);
        }

    }
}

int countRooms() {
    int rooms = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (adj[i][j] == '.') {
                DFS(i, j);
                rooms++;
            }
        }
    }

    return rooms;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> adj[i];
    }

    cout << countRooms() << '\n';

    return 0;
}

UVa :: 11709 :: Trust groups

Problem : Please find the problem here.

Explanation : Find the number of strongly connected components.  This can be done using Kosaraju's algorithm or Tarjan's Algorithm. I used the first one. Basically just do topological sort on the graph and then count the connected components with the DFS or BFS.

Code : Used Kosaraju's Algorithm.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e3;
int n, m;
string in;
map<string, int> node_id;
vector<int> adj[mxN], adjr[mxN], ts;
bool vis[mxN];

void dfs1(int u){
    vis[u] = 1;
    for(int v : adj[u]){
        if(!vis[v]){
	    dfs1(v);
	}
    }
    ts.push_back(u);
}

void dfs2(int u){
    vis[u] = 1;
    for(int v : adjr[u]){
	if(!vis[v]){
	    dfs2(v);
	}
    }
}

// Kosaraju's Algorithm

int SCC_count(){
	
    for(int i = 0; i < n; i++){
	if(!vis[i]){
	    dfs1(i);
	}
    }
    reverse(ts.begin(), ts.end());
    memset(vis, false, sizeof(vis));
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!vis[ts[i]]){
	    dfs2(ts[i]), cnt++;
	}
    }
    return cnt;
}

void init(){
    memset(vis, false, sizeof(vis));
    ts.clear();
    node_id.clear();
    for(int i = 0; i < n; i++){
        adj[i].clear();
	adjr[i].clear();
    }
}

int main()
{
    while(cin >> n >> m && (n || m)){
        init();
	cin.ignore();
	int id = 0;
	for(int i = 0; i < n; i++){
	    getline(cin, in);
	    if(node_id.find(in) == node_id.end()){
		node_id[in] = id++;
	    }
	}
	for(int i = 0, u, v; i < m; i++){
	    getline(cin, in);
	    u = node_id[in];
	    getline(cin, in);
	    v = node_id[in];
	    adj[u].emplace_back(v);
	    adjr[v].emplace_back(u);
        }
	cout << SCC_count() << '\n';
    }	
    return 0;
}

UVa : 11770 :: Lighting Away

Problem : Please find the problem here.

Explanation : Find the strongly connected components.  Basically just do topological sort on the graph and then count the connected components with the DFS or BFS.

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e4;
int n, m;
vector<int> adj[mxN], ts;
bool vis[mxN];

void dfs(int u){
    vis[u] = 1;

    for(int v : adj[u]){
	if(!vis[v]){
	    dfs(v);
	}
    }
    ts.push_back(u);
}

void init(){
    memset(vis, false, sizeof(vis));
    ts.clear();
    for(int i = 0; i < n; i++){
	adj[i].clear();
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
	cin >> n >> m;
	init();
	for(int j = 0, u, v; j < m; j++){
	    cin >> u >> v, u--, v--;
	    adj[u].emplace_back(v);
	}

        // doing topological sort;
        for(int j = 0; j < n; j++){
	    if(!vis[j]) dfs(j);
        }
        reverse(ts.begin(), ts.end());

        memset(vis, false, sizeof(vis));	
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if(!vis[ts[j]]) dfs(ts[j]), cnt++;
        }
        cout <<"Case " << i << ": " << cnt << '\n';

    }	
    return 0;
}

Uva : 10199 :: Tourist Guide

Problem : Please find the problem here.

Explanation : Count the number of bridges in the graph

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100;
int n, m, tin[mxN], low[mxN], timer;
string in, in2;
vector<int> adj[mxN];
map<string, int> node_id;
map<int, string> node_name;
set<string> ans;
bool vis[mxN];

void dfs(int u, int pu = -1){
    vis[u] = 1;
    tin[u] = low[u] = timer++;
    int children = 0;
    for(int v : adj[u]){
	if(v == pu) continue;
	if(vis[v]){
	    low[u] = min(low[u], tin[v]);
	}else{
	    dfs(v,u);
	    low[u] = min(low[u], low[v]);
	    if(low[v] >= tin[u] && pu != -1){
	        ans.insert(node_name[u]);
	    }
	    children++;
	}	
    }
    if(pu == -1 && children > 1){
	ans.insert(node_name[u]);
    }
}

void init(){
    memset(vis, false, sizeof(vis));
    memset(tin, -1, sizeof(tin));
    memset(low, -1, sizeof(low));
    for(int i = 0; i < n; i++){
	adj[i].clear();
    }
    node_id.clear();
    node_name.clear();
    ans.clear();
    timer = 0;
}

int main()
{
    ofstream fout("out");
    int __map = 1;
    cin >> n;
    while(1){
        if(n == 0){
	    break;
	}
	init();
	int id = 0;
	for(int i = 0; i < n; i++){
	    cin >> in;
	    node_id[in] = id;
	    node_name[id] = in;
	    id++;
	}
	cin >> m;
	for(int i = 0; i < m; i++){
            cin >> in >> in2;
	    adj[node_id[in]].emplace_back(node_id[in2]);
	    adj[node_id[in2]].emplace_back(node_id[in]);
	}
	for(int i = 0; i < n; i++){
	    if(!vis[i]) dfs(i);
	}
	printf("City map #%d: %d camera(s) found\n", __map, (int)ans.size());
	fout << "City map #" << __map++ <<": " << (int)ans.size() << " camera(s) found\n";
	for(string a : ans){
	    cout << a << '\n';
	    fout << a<< '\n';
	}
	cin >> n;
	if(n == 0){
	    break;
	}
	cout << '\n';
	fout << '\n';
    }
    return 0;
}

UVa : 315 :: Network

Problem : Please find the problem here.

Explanation : The problem basically asks to find the number of articulation points in the graph which can be done in using DFS with O(N+M) time complexity.

An Articulation Point is the verticex in the graph which when removed along with its associated edges, disconnects the graph.  

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100;
int n, m, tin[mxN], low[mxN], timer, cnt;
bool vis[mxN];
string in;
vector<int> adj[mxN];
set<int> ans;

void dfs(int u, int pu = -1){

    vis[u] = 1;
    tin[u] = low[u] = timer++;
    int children = 0;
    for(int v : adj[u]){
	if(v == pu) continue;
	if(vis[v]){
	    low[u] = min(low[u], tin[v]);
	}else{
	    dfs(v, u);
	    low[u] = min(low[u], low[v]);
	    if(low[v] >= tin[u] && pu != -1){
		ans.insert(u);
		cnt++;
	    }
	    ++children;
	}
    }
    if(pu == -1 && children > 1){
	ans.insert(u);
	cnt++;
    }
}

void init(){
    timer = 0;
    cnt = 0;
    ans.clear();
    memset(vis, false, sizeof(vis));
    memset(tin, -1, sizeof(tin));
    memset(low, -1, sizeof(low));
    for(int i = 0; i < n; i++){

        adj[i].clear();
    }
}

int main()
{
    while(1){
	cin >> n;
	if(n == 0){
	    break;
	}
	init();
	cin.ignore();
	while(1){
	    getline(cin, in);
	    stringstream ss(in);
	    int u, v;
	    ss >> u;
	    if(u == 0){
		break;
	    }
	    while(ss >> v){
	        adj[u-1].emplace_back(v-1);
		adj[v-1].emplace_back(u-1);
	    }
	}
	for(int i = 0; i < n; i++){
	    if(!vis[i]) dfs(i);
	}
	cout << ans.size() << '\n';
    }	
    return 0;
}

UVa : 260 :: II Gioco dell'X

Problem : Please find the problem here.

Explanation : Check, for black, if there's path from first row to last row OR for white, if there's path from first column to last column. Notice that as stated in the problem statement that both black and white can never win, its either black or white, that means you dont need to check for both white and black, as if one wins, other loses ans vice-versa. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 200, di[6]={-1, -1, 0, 0, 1, 1}, dj[6]={-1, 0, -1, 1, 0, 1};
int n;
string s[mxN];
bool vis[mxN][mxN];

bool isok(int i, int j){
	return i>=0 && i<n && j>=0 && j< n && !vis[i][j];
}

void dfs(int i, int j){
	vis[i][j] = 1; 
	for(int k = 0; k < 6; k++){
		int ni = i+di[k], nj = j+dj[k];
		if(isok(ni, nj) && s[ni][nj] == s[i][j]){
			dfs(ni, nj);
		}
	}
}

int main()
{	
	ofstream fout("out");
	int t = 1;
	while(cin >> n  && n){
		for(int i = 0; i < n; i++){
			cin >> s[i];
		}
		bool ok = 0;
		memset(vis, false, sizeof(vis));
		for(int i = 0; i < n; i++){
			if(s[i][0] == 'w'){
				dfs(i, 0);
			}
		}
		for(int i = 0; i < n; i++){
			if(vis[i][n-1]){
				ok = 1;
				break;
			}
		}
		cout << t++ << ' ' << (ok?'W':'B') << '\n';
	}	
	return 0;
}

UVa : 784 :: Maze Exploration

Problem : Please find the problem here.

Explanation : Simple DFS. 

Code :

#include <bits/stdc++.h>
using namespace std;

const int mxN = 30, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m, si, sj;
string s[mxN], in, br;

bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<(int)s[i].length() && s[i][j] == ' ';
}

void dfs(int i, int j){
    s[i][j] = '#'; 
    for(int k = 0; k < 4; k++){
	int ni = i+di[k], nj = j+dj[k];
	if(isok(ni, nj)){
	    dfs(ni, nj);
	}
    }
}

int main()
{	
    ofstream fout("out");
    int t;
    cin >> t;
    getline(cin, in); // read the newline character at the start
    for(int k = 0; k < t; k++){
	in.clear();
	getline(cin, in);  // read maze from here
	int i = 0;
	while(1){
	    if(in[0] == '_'){ // break if hit the partition line
		br = in;
		break;
	    }
	    s[i] = in;
	    for(int j = 0; j < (int)s[i].length(); j++){
		if(s[i][j] == '*'){
		    si = i, sj = j; s[i][j] = '#';
		}
	    }
	    i++;
	    getline(cin, in);
	}
	n = i
	dfs(si, sj);
	for(int j = 0; j < n; j++){
	    cout << s[j] << '\n';
	}
	cout << br << '\n';
    }
    return 0;
}

UVa : 785 :: Grid Colouring

Problem : Please find the problem here.

Explanation : Just need to traverse the graph, could be solved by DFS or BFS. Input parsing is troublesome though. Good for practice.  

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 32, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m;
string s[mxN], in, br;
char contour;

bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<(int)s[i].length() && s[i][j] == ' ';
}

void dfs(int i, int j, char c){
    s[i][j] = c;
    for(int k = 0; k < 4; k++){
        int ni = i+di[k], nj = j+dj[k];
	if(s[ni][nj] != c && isok(ni, nj)){ 
	    dfs(ni, nj, c);
	}
    }
}

int main()
{
    ofstream fout("out");
    while(getline(cin, in)){
	int i = 0;
	do{
	    if(in[0] == '_'){
	        br = in;
	        break;
	    }
	    s[i] = in;

	    // lazy way to find contour,
	    if(i == 0){
		for(int j = 1; j < (int)in.length(); j++){
		    if(in[j]!=' ' && in[j]!='_' && in[j]==in[j-1]){
			contour = in[j];
			break;
		    }
		}
	    }
	    // ends here
	    i++;
	}while(getline(cin, in));
	

        n = i;

        // now look for marker and apply dfs from that point.
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < (int)s[i].length(); j++){
		if(s[i][j] != contour && s[i][j] != ' ' && s[i][j] != '\t'){
		    dfs(i, j, s[i][j]);
		}
	    }
	}

	// finally print the grid.
	for(int i = 0; i < n; i++){
	    cout << s[i] << '\n';
	}

	// dont forget the seperation line -> "_______"
	cout << br << '\n';
    }	
    return 0;
}

UVa : 10926 :: How Many Dependencies?

Problem : Please find the problem here.

Explanation : We are basically asked to find a node with highest degree or find a connected component with highest number of nodes and print any one node from it. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100;
int t, n, m, cnt;
vector<int> adj[mxN];
bool vis[mxN];

void dfs(int u){
	vis[u] = 1;
	for(int v : adj[u]){
		if(!vis[v])
			dfs(v);
	}
	cnt++;
}

void init(){
	for(int i = 0; i < n; i++){
		adj[i].clear();
	}
	cnt = 0;
	memset(vis, 0, sizeof(vis));
}

int main()
{
	while(cin >> n && n){
		init();
		for(int i = 0, u, v; i < n; i++){
			cin >> u;
			for(int j = 0; j < u; j++){
				cin >> v, v--;
				adj[i].emplace_back(v);
			}
		}
		int index = INT_MAX;
		int d = -1;
		for(int i = 0; i < n; i++){
			memset(vis, 0, sizeof(vis));
			cnt = 0;
			dfs(i);
			if(cnt > d){
				d = cnt;
				index = i;
			}else if(cnt == d){
				index = min(i, index);
			}	
		}
		cout << index+1 << '\n';
	}	
	return 0;
}
	

UVa : 11518 :: Dominos 2

Problem : Please find the problem here.

Explanation : simply count the connected components. Also checkout UVa-11504-Dominos. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100, di[8]={1, 0, -1, 0, -1, -1, 1, 1}, dj[8]={0, 1, 0, -1, -1, 1, -1, 1};
int n, m, ans;
vector<int> disjoint_sets(10000);
string s[mxN], in;
bool vis[mxN][mxN];


bool isok(int i, int j){
	return i>=0 && i<n && j>=0 && j<m && s[i][j]=='W' && !vis[i][j]; 
}

void dfs(int i, int j){
	vis[i][j] = 1;
	for(int k = 0; k < 8; k++){
		int ni = i + di[k], nj = j + dj[k];
		if(isok(ni, nj)){
			dfs(ni, nj);
		}
	}
	ans++;
}

int main()
{
	int t;
	cin >> t;
	getline(cin, in);
	getline(cin, in);
	for(int c = 0; c < t; c++){
		getline(cin, in); 
		int k = 0;
		while(1){
			if(in.length() == 0 || (in[0] != 'L' && in[0] !='W')){
				break;
			}
			s[k++] = in;
			getline(cin, in);
		}
		n = k, m = s[0].length();
		memset(vis, false, sizeof(vis));
		if(c != 0){
			cout << '\n';
		}
		while(1){
			stringstream ss(in);
			int u, v;
			ss >> u;
		    ss >> v;
			u--, v--;
			ans = 0;
			memset(vis, 0, sizeof(vis));
			dfs(u, v);
			cout << ans << '\n';	
			if(cin.eof()){
				break;
			}
			getline(cin, in);
			if(in.length() == 0){
				break;
			}
		}
	}	
	return 0;
}

UVa : 469 :: Wetlands of Florida

Problem : Please find the problem here.

Explanation : The Problem basically asks to count the number of connected components in the grid, similiar to the problem Graph connectivity, once again the input format was annoying.

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100, di[8]={1, 0, -1, 0, -1, -1, 1, 1}, dj[8]={0, 1, 0, -1, -1, 1, -1, 1};
int n, m, ans;
vector<int> disjoint_sets(10000);
string s[mxN], in;
bool vis[mxN][mxN];


bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<m && s[i][j]=='W' && !vis[i][j]; 
}

void dfs(int i, int j){
    vis[i][j] = 1;
    for(int k = 0; k < 8; k++){
	int ni = i + di[k], nj = j + dj[k];
	if(isok(ni, nj)){
	    dfs(ni, nj);
	}
    }
    ans++;
}

int main()
{
    int t;
    cin >> t;
    getline(cin, in);
    getline(cin, in);
    for(int c = 0; c < t; c++){
	getline(cin, in); 
	int k = 0;
	while(1){
	    if(in.length() == 0 || (in[0] != 'L' && in[0] !='W')){
		break;
	    }
	    s[k++] = in;
	    getline(cin, in);
        }
	n = k, m = s[0].length();
	memset(vis, false, sizeof(vis));
	if(c != 0){
	    cout << '\n';
	}
	while(1){
	    stringstream ss(in);
	    int u, v;
	    ss >> u;
	    ss >> v;
	    u--, v--;
	    ans = 0;
	    memset(vis, 0, sizeof(vis));
	    dfs(u, v);
	    cout << ans << '\n';	
	    if(cin.eof()){

                break;
	    }
	    getline(cin, in);
	    if(in.length() == 0){
                break;
	    }
	}
    }	
    return 0;
}

UVa : 459 :: Graph Connectivity

Problem : Please find the problem here.

Explanation : Though the problem is easy and only asks for the number of connected components, the input parsing is tiresome and irritating. But still good for practice purpose. 

Code : Used DFS to count the number of connected components.

#include <bits/stdc++.h>
//#define debug

using namespace std;

const int mxN = 27;
string s, n;
int u, v, m;
vector<int> adj[mxN];
bool vis[mxN];

void dfs(int u){
	vis[u] = 1;
	for(int v : adj[u]){
		if(!vis[v]){
			dfs(v);
		}
	}
}

void init(){
	for(int i = 0; i < m; i++){
		adj[i].clear();
	}
	memset(vis, 0, sizeof(vis));
}

void set_values(){
	u = int(s[0]-'A');
	v = int(s[1]-'A');
#ifdef debug
	cout << u << ' ' << v << '\n';
#endif
}

int main()
{
	ofstream fout("out");
	int tt;
	cin >> tt;
	while(tt--){
		cin >> n;
		m = (int)(n[0]-'A')+1;
		init();
		getline(cin, s);
		while(1){
			getline(cin, s);
			if(s.length() == 0){
				break;
			}
			set_values();
			adj[u].emplace_back(v);
			adj[v].emplace_back(u);
		}

		int cnt = 0;
		for(int i = 0; i < m; i++){
			if(!vis[i]){
				dfs(i); cnt++;
			}
		}	
		if(tt){
			cout << cnt << "\n\n";
		}
		else{
			cout << cnt << '\n';
		}
	}
	return 0;
}