program deadlock;

type
    status = ( Allocated, Free );
    nameType = string;

    resource =  record
	name: nameType;
	state: status;
	holding: integer;
	waiting: array[1..100] of integer;
	numWaiting: integer;
    end;

var
    i: integer;
    id: integer;
    resources: array[1..100] of resource;
    waitingOn: array[1..100] of integer;
    lastResource: integer;
    done: boolean;
    pid: integer;
    resourceName: nameType;
    request: char;
    space: char;

function findAndAddResource(name: nameType): integer;
    var
	id: integer;
	i: integer;

begin
    id := -1;
    for i := 1 to lastResource do begin
	if (resources[i].name = name) then id := i;
    end;

    if (id = -1) then begin
	lastResource := lastResource + 1;
	resources[lastResource].name := name;
	resources[lastResource].state := Free;
	resources[lastResource].numWaiting := 0;
	id := lastResource;
    end;
    findAndAddResource := id;
end;

function checkDeadLock:boolean;
var
	inLoop: array[1..100] of boolean;
	i: integer;
	j: integer;
	done: boolean;
	current: integer;

begin

	checkDeadLock := false;
	done := false;
	for j := 1 to 100 do begin
	    for i := 1 to 100 do inLoop[i] := false;
	    current := j;
	    while (current <> -1) and not done do begin
		if inLoop[current] then begin
		    write('Deadlock detected: ');
		    for i := 1 to 100 do begin
			 if (inLoop[i]) then write(i:1, ' ');
		    end;
		    writeln;
		    current := -1;
		    checkDeadLock := true;
		    done := true;
		end else begin
		    inLoop[current] := true;
		    current := waitingOn[current];
		end;
	    end;
	end;
end;

function processRequest(pid: integer;
			 request: char;
			 resourceName: nameType): boolean;

var
    i: integer;

begin
    processRequest := false;
    id := findAndAddResource(resourceName);
    if (request = 'a') then begin 
	if (resources[id].state = Free) then begin
	    resources[id].state := Allocated;
	    resources[id].holding := pid;
	    waitingOn[pid] := -1;
	end else if (resources[id].holding = pid) then begin
	    writeln('Input Error');
	    processRequest := true;
	end else begin
	    resources[id].numWaiting := resources[id].numWaiting + 1;
	    resources[id].waiting[resources[id].numWaiting] := pid;
	    waitingOn[pid] := resources[id].holding;
	    { now check for deadlock }
	    processRequest := checkDeadLock;
	end;
    end else begin
	if (resources[id].state = Free) then begin
	    writeln('Input Error');
	    processRequest := true;
	end else begin
	    if (resources[id].numWaiting > 0) then begin
		resources[id].holding := resources[id].waiting[1];
		for i := 2 to resources[id].numWaiting do begin
		     resources[id].waiting[i-1] :=  resources[id].waiting[i];
		     waitingOn[resources[id].waiting[i]] := 
			 resources[id].holding;
		end;
		resources[id].numWaiting := resources[id].numWaiting - 1;
		waitingOn[resources[id].holding] := -1;
	    end else begin
		resources[id].state := Free;
	    end;
	end;
    end;
end;

begin
    done := false;
    for i := 1 to 100 do waitingOn[i] := -1;
    while (not done) do begin
	readln(pid, space, request, resourceName);
	if (pid <> -1) then begin
	    done := processRequest(pid, request, resourceName);
	end else  begin
	    writeln('No deadlocks found');
	    done := true;
	end;
    end;
end.