This problem has a greedy solution.. But apparently there is a DFS solution, which I am unable to get. Can anyone help?
Sort by starting city, and then by ending city. Can you process them in some order now to reach the answer?
Select the first road and arbitrarily assign 'N' or 'S'. Let the starting city be t1 and ending city be t2. Have you indirectly decided the signs for some other roads by this step?
Try to assign opposite signs to roads that start before t1 and end after t1(but before t2). Similarly try for roads starting before t2 and ending after t2. Do this recursively for all roads which were assigned a sign. If assigning opposite road is not possible(intersects some other road), then the answer is "NIE". Else after the recursive step ends, check for next road which hasn't been assigned a sign. Do this till there is a contradiction, or the solution has been obtained.