uVA :: 908 :: Re-connecting Computer Sites

Problem : Please find the problem here.

Explanation :The previously chosen path is already given so the first answer is just the sum of the cost of these paths. For the second cost, combine the original edges with the newly given edges and find the weight of the MST associated to that set of edges.

Code : Used Kruskal's Algorithm to find the MST.

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

const int mxN = 1e6;
int n, t, m, k;
int parent[mxN], ranks[mxN];

struct Edge{
    int src, dst, cost;
    
    Edge(int _src, int _dst, int _cost){
        src = _src;
        dst = _dst;
        cost = _cost;
    }

    bool operator<(Edge const &other){
        return cost < other.cost;
    }
};

void make_set(int v){
    parent[v] = v;
    ranks[v] = 0;
}

int find_set(int v){
    if(v == parent[v]){
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(ranks[a] < ranks[b]){
            swap(a, b);
        }
        parent[b] = a;
        if(ranks[a] == ranks[b]){
            ranks[a]++;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ofstream fout("out");
    bool first = 1;

    while(cin >> n){
        int src, dst, cost;
        vector<Edge> new_edges;
        int ans1 = 0, ans2 = 0;
        for(int i = 0; i < n-1; i++){
            cin >> src >> dst >> cost;
            //chosen_edges.emplace_back(Edge(src, dst, cost));
            ans1 += cost;
        }
        cin >> k;
        for(int i = 0; i < k; i++){
            cin >> src >> dst >> cost;
            new_edges.push_back(Edge(src, dst, cost));
        }
        cin >> m;
        for(int i = 0; i < m; i++){
            cin >> src >> dst >> cost;
            new_edges.emplace_back(Edge(src, dst, cost));
        }

        for(int i = 0; i < (int)new_edges.size(); i++){
            make_set(i);
        }

        sort(new_edges.begin(), new_edges.end());
        for(Edge e : new_edges){
            if(find_set(e.src) != find_set(e.dst)){
                ans2 += e.cost;
                union_sets(e.src, e.dst);
            }
        }
        if(!first){
            cout << '\n';
        }else{
            first = 0;
        }
        cout << ans1 << '\n';
        cout << ans2 << '\n';
    }
    return 0;
}

UVa :: 10986 :: Sending email

Problem : Please find the problem here.

Explanation : Given an undirected weighted graph, find the minimum distance between two given nodes. The problem is naive and clearly suggested to use the algorithm suited to calculate the SSSP.

Code : Used Dijkstra's Algorithm.

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

const int mxN = 2e5;
int n, m, s, t, d[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];


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

void solve(){
    cin >> n >> m >> s >> t;
    init();
    for(int i = 0, u, v, w; i < m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    priority_queue<array<int,2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    d[s] = 0;
    pq.push({0, s}); 
    while(pq.size()){
        array<int, 2> uu = pq.top();
        pq.pop();
        int u = uu[1];
        if(vis[u]) continue;
        vis[u] = 1;
        for(array<int, 2> vv : adj[u]){
            int v = vv[0], w = vv[1];
            if(d[v] > d[u]+w){
                d[v] = d[u]+w;
                pq.push({d[v], v});
            }
        }
    }
    if(d[t] == INT_MAX) cout << "unreachable\n";
    else cout << d[t] << '\n';
    
}

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

    int test_case;
    cin >> test_case;
    for(int i = 1; i <= test_case; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
    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 : 10946 :: You want what filled?

Problem : Please find the problem here.

Explanation : We are basically asked to find the connected components in the graph and print them in non increasing order along with the charcter in each connected component printed in increasing order. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define debug

const int mxN = 60, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m, cnt;
string s[mxN];
vector<pair<char, int>> ans;
bool vis[mxN][mxN];

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

bool cmp(pair<char, int> a, pair<char, int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second >= b.second;
}

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

int main()
{
    ofstream fout("out");
    int t = 1;
    while(cin >> n >> m && (n||m)){
        for(int i = 0; i < n; i++){
	    cin >> s[i];
        }
	memset(vis, false, sizeof(vis));
	ans.clear();
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++){
		if(isok(i, j)){
		    cnt = 0;
		    dfs(i, j);
		    ans.push_back(mp(s[i][j], cnt));
	        }
	    }
	}
	sort(ans.begin(), ans.end(), cmp);
	cout << "Problem " << t++ << ":\n";
	for(auto a : ans){
	    cout << a.first << ' ' << a.second << '\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;
}

UVa : 10765 :: Doves and Bombs

Problem : Please find the problem here.

Summary and Explanation : The problem asked to find the vertices with the maximum number of childrens. These vertices mostly (not entirely) are the Articulation points. Since we need to print m such vertices, if we run out of Articulation points in the graph then we can just print the ordinary vertices with maximum number of childs.
This problem is so general that I dont want to use the term articulation points, because we just need to print the nodes with maximum number of childrens with their node index in the order asked in the problem.

Code : Used DFS. Stored the number of childrens for each vertex. Notice at the end of DFS, the If condition is for cycles in the graph. In case of a cycle strating from the given node, the number of childrens for that node should be decreased by 1.

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

const int mxN = 1e4;
int n, m, u, v, timer, tin[mxN], low[mxN], c[mxN];
vector<int> adj[mxN];
array<int, 2> ans[mxN]; // index 0 strores the vertex no. | index 1 stores the number of childrens of the vertex;
bool vis[mxN];

bool cmp(array<int, 2> a, array<int, 2> b){
    if(a[1] != b[1]){
        return a[1] > b[1];
    }
    else{
        return a[0] < b[0];
    }
}

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 == u) 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[u][1]++;
            }
            c[u]++;
            children++;
        }
    }
    if(pu == -1 && children > 1){
        ans[u][1] = children-1;
    } 
}

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

int main()
{
    ofstream fout("out");
    while(scanf("%d %d", &n, &m) && (n&&m)){
        init();
        while(scanf("%d %d", &u, &v) && !(u == -1 || v == -1)){
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        for(int i = 0; i < n; i++){
            if(!vis[i]){
                dfs(i);
            }
        }
        sort(ans, ans+n, cmp);
        for(int i = 0; i < m; i++){
            cout << ans[i][0] << ' ' << ans[i][1]+1 << '\n';

        }
        cout << '\n';
    }
    return 0;
}