<commit_before>﻿using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Player
{
	static void Main(string[] args)
	{
		//Console.Error.WriteLine("Number of Nodes, Links, Gateways");
		string[] inputs;
		inputs = Console.ReadLine().Split(' ');
		int N = int.Parse(inputs[0]); // the total number of nodes in the level, including the gateways
		int L = int.Parse(inputs[1]); // the number of links
		int E = int.Parse(inputs[2]); // the number of exit gateways

		//Console.Error.WriteLine("All links, one per line");
		var links = new List<Tuple<string, string>>();
		for (int i = 0; i < L; i++)
		{
			inputs = Console.ReadLine().Split(' ');
			links.Add(new Tuple<string, string>(inputs[0], inputs[1]));
		}

		//Console.Error.WriteLine("All gateway node indexes, one per line");
		var gateways = new string[E];
		for (int i = 0; i < E; i++)
		{
			gateways[i] = Console.ReadLine(); // the index of a gateway node
		}

		// game loop
		while (true)
		{
			//Console.Error.WriteLine("Current SI position");
			var SI = Console.ReadLine(); // The index of the node on which the Skynet agent is positioned this turn

			var shortestPaths = new List<string[]>();
			foreach (var gateway in gateways)
			{
				var algorithm = new Dijkstra(links);
				var path = algorithm.Path(SI, gateway);
				Console.Error.Write("Shortest path to gateway " + gateway + ": ");
				Console.Error.WriteLine(path == null ? "(none)" : string.Join(", ", path));
	
				if (path != null)
				{
					if (shortestPaths.Count == 0 || path.Length < shortestPaths.First().Length)
					{
						shortestPaths.Clear();
						shortestPaths.Add(path);
					}
					else if (path.Length == shortestPaths.First().Length)
					{
						shortestPaths.Add(path);
					}
				}
			}

			if (!shortestPaths.Any())
			{
				Console.Error.WriteLine("No path left. I won!");
				Console.ReadLine();
				break;
			}


			var linksToChooseFrom = shortestPaths.Select(path => path.Reverse().Take(2).Reverse()).ToArray();
			foreach (var link in linksToChooseFrom)
			{
				Console.Error.WriteLine("Possible link: " + string.Join(" - ", link));
			}
			var linkToSevere = linksToChooseFrom.GroupBy(link => link.First()).OrderByDescending(grp => grp.Count()).First().First();
			//var linkToSevere = linksToChooseFrom.First();


			Console.WriteLine(string.Join(" ", linkToSevere));
			links.Remove(new Tuple<string, string>(linkToSevere.First(), linkToSevere.Last()));
			links.Remove(new Tuple<string, string>(linkToSevere.Last(), linkToSevere.First()));
		}
	}



	class Dijkstra
	{
		class Node
		{
			public Node(string name)<commit_msg>Passing all but last test in hard mode.<commit_after>﻿using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Player
{
	static void Main(string[] args)
	{
		//Console.Error.WriteLine("Number of Nodes, Links, Gateways");
		string[] inputs;
		inputs = Console.ReadLine().Split(' ');
		int N = int.Parse(inputs[0]); // the total number of nodes in the level, including the gateways
		int L = int.Parse(inputs[1]); // the number of links
		int E = int.Parse(inputs[2]); // the number of exit gateways

		//Console.Error.WriteLine("All links, one per line");
		var links = new List<Tuple<string, string>>();
		for (int i = 0; i < L; i++)
		{
			inputs = Console.ReadLine().Split(' ');
			links.Add(new Tuple<string, string>(inputs[0], inputs[1]));
		}

		//Console.Error.WriteLine("All gateway node indexes, one per line");
		var gateways = new string[E];
		for (int i = 0; i < E; i++)
		{
			gateways[i] = Console.ReadLine(); // the index of a gateway node
		}

		// game loop
		while (true)
		{
			//Console.Error.WriteLine("Current SI position");
			var SI = Console.ReadLine(); // The index of the node on which the Skynet agent is positioned this turn


			var gatewayLinks = links.Where(x=>gateways.Intersect(new[]{x.Item1, x.Item2}).Any()).ToArray();
			var nodesInFrontOfGateways = gatewayLinks.SelectMany(x => new[] { x.Item1, x.Item2 }).Except(gateways)
				.Distinct();
			//foreach (var node in nodesInFrontOfGateways)
			//{
			//	Console.Error.WriteLine(node + " is in front of one or more gateways");
			//}

			var nodesWithLinks = nodesInFrontOfGateways.Select(node => new
			{
				Node = node,
				Links = links.Where(link =>
						link.Item1 == node && gateways.Contains(link.Item2)
					|| link.Item2 == node && gateways.Contains(link.Item1)
					).ToArray()
			}).ToArray();



			var scoredNodes = new List<Tuple<string, int, Tuple<string, string>[], double>>();
			foreach (var node in nodesWithLinks)
			{
				var algorithm = new Dijkstra(links);
				var path = algorithm.Path(SI, node.Node);

				if (path != null)
				{
					var score = path.Length == 0 
						? double.MaxValue 
						: node.Links.Count() / ((double)path.Length - 1);
					if (node.Links.Count() > 1)
						score += 1000;
					scoredNodes.Add(new Tuple<string, int, Tuple<string, string>[], double>(node.Node, path.Length, node.Links, score));
				}
			}

			foreach (var node in scoredNodes.OrderByDescending(x => x.Item4))
			{
				Console.Error.WriteLine(node.Item1 + " is " + node.Item2 + " steps away and has " + node.Item3.Length + " gateway links => Score = " + node.Item4);
			}
			//Tuple<string, double, Tuple<string, string>> mostCriticalNode = null;
			var mostCriticalNode = scoredNodes.OrderByDescending(x => x.Item4).First();

			//if (mostCriticalNode == null)
			//{
			//	Console.Error.WriteLine("No path left. I won!");
			//	Console.ReadLine();
			//	break;
			//}


			var linkToSevere = mostCriticalNode.Item3.First();
			Console.WriteLine(linkToSevere.Item1 + " " + linkToSevere.Item2);
			links.Remove(linkToSevere);
		}
	}



	class Dijkstra
	{
		class Node
		{
			public Node(string name)
{'fraction_non_alphanumeric': 0.15258408531583265, 'fraction_numerical': 0.006562756357670222, 'mean_word_length': 3.323404255319149, 'pattern_counts': {'":': 1, '<': 24, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '894780', 'n_tokens_mistral': 2307, 'n_tokens_neox': 1933, 'n_words': 524}