Code:

void conditionTesting (int sticks, int lines, int **conditions){
int x;
int y;
int z;
int stickisbelow = 0;
int removed[sticks];
for (x = 0; x < sticks-1; x++)
{
removed[x] = 0;
}
//tests each stick to see if it can be removed
for (x = 1; x <= sticks; x++)
{
//will see if the stick is below any others, if it isn't, then it can be removed.
for (y = 0; y < lines; y++)
{
if (x == conditions[y][1])
{
//increments if it finds the stick below any others
//if it doesn't increment, that means that the stick is only above
stickisbelow++;
}
}
//if it only is above, then it will remove it from the above columnn and it moves all the sticks that were below it to the above column
//will also keep track of sticks removed.
if (stickisbelow == 0)
{
for (z = 0; z < lines; z++)
{
if (x == conditions[z][0])
{
conditions[z][0] = conditions[z][1];
conditions[z][1] = 0;
removed[x]++;
}
}
}
}
//checks to see if all sticks removed, if all the spots are 0 in the array
int notremoved = 0;
for (x = 0; x < lines; x++)
{
if (conditions[x][0] != 0 || conditions[x][1] != 0)
{
notremoved++;
}
}
if (notremoved == 0)
{
printf("Valid\n");
}
else
{
printf("Impossible\n");
}
}

It will take this long if you are checking

if each stick is below another and repeating check until you find it's impossible or if all the sticks are removed.

Is this similar to what you are talking about with the lists?

This isn't full, but it explains what i was working on. I know there must be a faster one, since we are supposed to get it to be able to return an answer in under a minute.